一类新的优美树

Another Gracefull Trees

Rosa等人于1966年提出了著名的优美树猜想,即任何树都是优美图。该猜想至今没有得到证明或否定,仅有一些特殊树类被证明是优美图。通过构造路Pn=v0v1…vn的平衡标号f使f(v0)=k,其中k为任意不大于n的非负整数,且4k≠n,3n,进而给出一种新的优美树的构造方法,使已知的优美树大大增加。

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, 3 n, there exists a bipartited labeling f of path Pn = v0 v1 … vn such 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.