Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649311 | Discrete Mathematics | 2009 | 10 Pages |
Abstract
A graceful labeling of a graph G=(V,E)G=(V,E) assigns |V||V| distinct integers from the set {0,…,|E|}{0,…,|E|} to the vertices of GG so that the absolute values of their differences on the |E||E| edges of GG constitute the set {1,…,|E|}{1,…,|E|}. A graph is graceful if it admits a graceful labeling. The forty-year old Graceful Tree Conjecture, due to Ringel and Kotzig, states that every tree is graceful.We prove a Substitution Theorem for graceful trees, which enables the construction of a larger graceful tree through combining smaller and not necessarily identical graceful trees. We present applications of the Substitution Theorem, which generalize earlier constructions combining smaller trees.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Marios Mavronicolas, Loizos Michael,