| 引用本文: | 戴丽,王正华,谢政.一类新的优美树.[J].国防科技大学学报,2008,30(1):129-132.[点击复制] |
| DAI Li,WANG Zhenghua,XIE Zheng.Another Gracefull Trees[J].Journal of National University of Defense Technology,2008,30(1):129-132[点击复制] |
|
| |
|
|
| 本文已被：浏览 7356次 下载 6043次 |
| 一类新的优美树 |
| 戴丽, 王正华, 谢政 |
|
(国防科技大学 理学院，湖南 长沙 410073)
|
| 摘要: |
| Rosa等人于1966年提出了著名的优美树猜想，即任何树都是优美图。该猜想至今没有得到证明或否定，仅有一些特殊树类被证明是优美图。通过构造路 Pn=v0v1…vn的平衡标号f使f(v0)=k，其中k为任意不大于n的非负整数，且4k≠n，3n，进而给出一种新的优美树的构造方法，使已知的优美树大大增加。 |
| 关键词: 优美图 顶点标号 平衡标号 路 |
| DOI： |
| 投稿日期：2007-07-08 |
| 基金项目: |
|
| Another Gracefull Trees |
| DAI Li, WANG Zhenghua, XIE Zheng |
|
(College of Science, National Univ. of Defense Technology，Changsha 410073，China)
|
| Abstract: |
| In 1966, Rosa conjectured that all trees are graceful, which has ever since been considered the famous Graceful Tree Conjecture (GTC). Now the conjecture still remains to be an open problem, and only a few kinds of trees are proved to be graceful. The number, however, can be enlarged by the approach presented in the paper. For any integer k∈｛0，1，2，…，n｝and 4k≠n，3n, there exists a bipartited labeling f of path Pn=v0v1…vnsuch that f(v0)=k . Based on this, a method for constructing bigger graceful trees by joining a path to a graceful tree is given and this makes much more trees to be graceful. |
| Keywords: graceful graph vertex labeling balanced labeling path |
|
|
|
|
|
