Does every “balloon” (dragon, tadpole, canoe paddle) admit a graceful labeling?

Question

8/18/14 Edit: If anyone has a copy of a related reference, then I would be happy to see it. For now, I am accepting the answer below and considering the question answered in the affirmative: Yes.

---

Earlier Edit: It appears that the answer is "yes," either by an already existent publication or by combining the Guo reference mentioned below with the answer here (and a remark on cycles admitting graceful labelings). But I have not been able to track down an accessible reference, and hope that someone can find one!

---

Note: Perry Iverson points out that the graphs described below go by different names, and suggests an answer already exists in the literature. I am adding a reference-request tag in the hopes that someone can find a proof of the full characterization. According to Gallian's A Dynamic Survey of Graph Labeling (pdf), there is some work due to Wenfu Guo, who (from the citation below) is using notation similar to mine - even if they are called dragons rather than balloons.

However, it is clear that the proof alluded to below is not bidirectional (or is mis-stated) since it discusses only the cases when the cycle is congruent to $1$ or $2$ (mod $4$), yet Leen Droogendijk's approach can be extended to gracefully label $B(n,k)$ whenever $n \equiv 0$ or $3$ (mod $4$); precisely the complementary cases! Moreover, the image from Wikipedia clearly shows a graceful labeling in which the cycle is congruent to $3$ (mod $4$).

I will gladly accept an answer with an accessible version of the work by Guo (or by anyone else who has managed a characterization of such graphs).

---

The wikipage on graceful labelings includes the following diagram:

Quoting from the page:

In graph theory, a graceful labeling of a graph with $m$ edges is a labeling of its vertices with some subset of the integers between $0$ and $m$ inclusive, such that no two vertices share a label, and such that each edge is uniquely identified by the positive, or absolute difference between its endpoints.

Let us call a graph a balloon if it consists of an $n$-cycle with a single strand (string) emanating from one of the vertices in the aforementioned cycle. Furthermore, let us require the balloon component to have $n \geq 3$ vertices and the string component to have an additional $k \geq 1$ vertices; in such a case, we denote the balloon as $B(n,k)$.

For example, the diagram above depicts $B(3,2)$, i.e., a balloon with a $3$-cycle (the vertices labeled $0, 4, 5$ make up the balloon component) and a length $2$ string (emanating from the vertex $0$).

Fact: For all $k \geq 1$, the balloon $B(3,k)$ admits a graceful labeling.

(Proof: Left to reader.)

Question: Which balloons admit graceful labelings?

For example, can anyone prove that $B(4,k)$ admits a graceful labeling for all $k \geq 1$?

Alternatively, can anyone come up with an $n \geq 3$ and $k \geq 1$ for which $B(n,k)$ does not admit a graceful labeling?

A word of caution: The conjecture that all trees admit graceful labelings is a notoriously difficult open problem. (For a related MSE post, see here.) Ideally, I would wish for a full characterization of the gracefulness of balloons; however, I will certainly up-vote responses with non-trivial contributions (and may simply "accept" one, particularly if the question here can be transformed into one that implies the conjecture for trees).

Answer 1

Every $B(4,k)$ admits a graceful labeling. We prove this by induction on $k$.

Our induction hypothesis is: every $B(4,k)$ admits a graceful labeling where the vertex of degree 1 has label 0. For $k=1$ we cyclically assign the labels $1,4,3,5$ to the vertices of the cycle. Then add one pending edge to the vertex with label $5$ and give the last vertex label 0. It is trivially verified that this defines a graceful labeling.

For the induction step: take a $B(4,k)$ with a graceful labeling where the vertex of degree 1 has label 0. Now prolong the path with one more edge and give the new vertex label $k+5$. We now have a graceful labeling of $B(4,k+1)$. Finally invert that labeling (i.e. replace each label $x$ by $k+5-x$ and we end up with a graceful labeling of $B(4,k+1)$ with $0$ on the vertex of degree 1.

Note that this procedure generalizes to all $B(n,k)$, where $C_n$ is graceful.

Answer 2

Unfortunately I do not know how to access the referred document, so I have done some (computer-assisted) research on this, specifically for $B(5,k)$.

This graph has $k+5$ vertices, so it will use vertex labels from $[0,k+5]$ (omitting only one of them). In the arrays following the vertices along the cycle have index $0,1,2,3,4$ and the vertices of the path start at index 5 which is connected to the cycle-vertex with index 0. The first 6 vertices always get labels $[0,1,k+3,2,k+5,k+4]$ and then the 7th vertex must have label 4, This creates the edge labels $1,k,k+1,k+2,k+3,k+4,k+5$ on the first 7 edges.

Now you can fix these edge labels and run a computer program that finishes the labeling for you. The number of possibilities soon gets large, but if you focus on the edge labels you will soon detect that final sequences reappear. More concretely: if we have an edge list for $B(5,k)$ as above, then the last $n+k-7$ entries on this list reappear as the end of an edge list for $B(5,k+3)$.

And once this is detected, it is not very hard to explain. Let $L=[0,1,k+3,2,k+5,k+4,4,a_1,\ldots,a_{5+k-7}]$ a graceful labeling for $B(5,k)$, and $k'=k+3$. We claim that $L'=[0,1,k'+3,2,k'+5,k'+4,4,k'+2,3,k',a'_1,\ldots,a'_{5+k-7}]$ (where $a'_i=k'+4-a_i$) is a graceful labeling for $B(5,k')$. Note that we replaced the first 7 labels by the defined start pattern for $k'$, then inserted 3 vertex labels ($k'+2,3,k'$) and finally 'inverted' the rest of the pattern.

Of course we need to prove this claim. Because $L$ is a graceful labeling the last $5+k-7$ vertex labels are in $\{3,5,\ldots,k+2\}$ and all different, so the last $5+k-7$ vertex labels of $L'$ are in $\{k'+4-3,k'+4-5,\ldots,k'+4-(k+2)\}=\{5,\ldots,k'-1,k'+1\}$ (and still all different). Now straight inspection shows that $L'$ has all different labels from $[0,k'+5]$.

The edge labels for the first seven edges of $L$ were $1,k,k+1,k+2,k+3,k+4,k+5$, the next edge label is $a_1-4$ and the other edge labels are the missing ones from $[1,k+5]$. The first seven edge labels of $L'$ are $1,k',k'+1,k'+2,k'+3,k'+4,k'+5$, the next four edge labels are $\{(k'+2)-4,(k'+2)-3,k'-3,k'-a'_1\}=\{k'-2,k'-1,k'-3,a_1-4\}$ (remember that $a'_i=k'+4-a_i$) and the rest are identical to the rest of $L$, since our 'inversion' does not change the absolute value of the differences.

Again straight inspection shows that we have found all possible values exactly once, which finishes the proof of our claim.

To finish our proof we provide explicit graceful labelings for

$B(5,1)$: [0,1,4,2,6,5]
$B(5,2)$: [0,1,5,2,7,6,4]
$B(5,3)$: [0,1,6,3,7,8,2,4]

$B(5,4)$: [0,1,7,2,9,8,4,6,3]
$B(5,5)$: [0,1,8,2,10,9,4,6,3,7]
$B(5,6)$: [0,1,9,2,11,10,4,7,3,8,6]

and the cyclic nature (period 3) of these labelings will provide a proof by induction.

Note that for $k\leq 3$, $B(5,k)$ is still graceful, but the labeling is not always in the format we desire, so we start our induction at $k=4,5,6$.

TODO: check if this mechanism can be generalized (not sure if I will continue working on this: the problem is not very important).

Remark: it turned out that the value for $k$ I used was one off compared to the one used in the question. I hope I fixed them all, but let me know if you find an 'off by one' error.