Article ID Journal Published Year Pages File Type
4649311 Discrete Mathematics 2009 10 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,