New graceful diameter-6 trees by transfers

Abstract

Given a graph $G$, a labeling of $G$ is an injective function $f:V(G)\to {\mathbb{Z}}_{\ge 0}$. Under the labeling $f$, the label of a vertex $v$ is $f(v)$, and the induced label of an edge $uv$ is $|f(u)-f(v)|$. The labeling $f$ is graceful if the labels of the vertices are $\{0,1,\dots ,|V(G)|-1\}$, and the induced labels of the edges are distinct. The graph $G$ is graceful if it has a graceful labeling. The Graceful Tree Conjecture, introduced by Kotzig in the late 1960's, states that all trees are graceful. It is an open problem whether every diameter-6 tree has a graceful labeling. In this paper, we prove that if $T$ is a tree with central vertex and root $v$, such that each vertex not in the last two levels has an odd number of children, and $T$ satisfies one of the following conditions (a)-(e), then $T$ has a graceful labeling $f$ with $f(v)=0$: (a) $T$ is a diameter-6 complete tree; (b) $T$ is a diameter-6 tree such that no two leaves of distance 2 from $v$ are siblings, and each leaf of distance 2 from $v$ has a sibling with an even number of children; (c) $T$ is a diameter-$2r$ complete tree, such that the number of vertices of distance $r-1$ from $v$, with an even number of children, is not $3(\mathrm{mod}4)$; (d) $T$ is a diameter-$2r$ tree, such that the number of vertices of distance $r-1$ from $v$, with an even number of children, is not $3(\mathrm{mod}4)$, no two leaves of distance $r-1$ from $v$ are siblings, and each leaf of distance $r-1$ from $v$ has a sibling with an even number of children; (e) $T$ is a diameter-6 tree, such that each internal vertex has an odd number of children. In particular, all depth-3 trees of which each internal vertex has an odd number of children are graceful.

arXiv commentThis paper is based on my undergraduate senior thesis for the math department at Princeton University, from which I graduated in June 2013