The subdivision graph of a graceful tree is a graceful tree

✍ Scribed by M. Burzio; G. Ferrarese

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 253 KB
• Volume: 181
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(97)00069-1

✦ Synopsis

Koh, Rogers and Tan (Discrete Math. 25 (1979) [141][142][143][144][145][146][147][148] give a method to construct a bigger graceful tree from two graceful trees. Based upon their results, we give a new construction, which allows us to prove that the subdivision graph of a graceful tree is still a graceful tree.

According to [4], let T(n) be a tree on n vertices. A valuation on T(n), is a bijection 0 from the vertex-set of T(n) onto the set N = {1,2 ..... n}. For each edge uv in T(n), the weight of uv, denoted by O(uv), is the value ]0(u) -O(v)l. The system (T(n), O) is said to be 9raceful if the weights of all edges of T(n) are distinct, then are exactly the integers {1,2 ..... n -1 }. A tree T is called a 9raceful tree if there exists a valuation 0 on T, such that the system (T,O) is graceful. In this case, 0 is called a ,qraceJul valuation on T.