Graceful Graphs / Graceful Labellings of Cones

Created: Mar 1, 1993; last updated: May 26, 2014

Introduction

Here are my results, conjectures, and code for labeling the generalized cone graphs.

Gallian's A Dynamic Survey of Graph Labelling lists double cones as a family of graphs whose gracefulness is unknown. I began investigating these graphs, but quickly switched to the generalized cone $Cone(m,n) = C_m + \overline{K_n}$ for $m,n > 0$ (where $\overline{G}$ denotes the graph complement of G). These graphs have many cycles and symmetries.

In 1994, I found graceful labelings for all the cases $m=2,3,4,5,7,8, \forall n$. These labelings and other results are published below.

Summary of Known Results

Cone(m,n)	m=1	m=2	m=3	m=4	m=5	m=6	m=7	m=8	m=9	m=10	m=11	m=12	m=13	...	comments
n=0	Y	Y	Y	Y	N	N	Y	Y	N	N	Y	Y	N		cycles, Y iff $m \equiv 0,3\pmod{4}$ or m=1,2
n=1	Y	Y	Y	Y	Y	Y	Y	Y	Y	Y	Y	Y	Y	Y	wheels, Y $\forall m$
n=2	Y	Y	Y	Y	Y	N	Y	Y	Y	N	Y	Y	?	?	double cones, ?, N ∀m =6+4k
n=3	Y	Y	Y	Y	Y	Y	Y	Y	Y	?	Y	Y	?	?	?
n=4	Y	Y	Y	Y	Y	N	Y	Y	Y	N	Y	Y	?	?	?, N ∀m =6+4k
n=5	Y	Y	Y	Y	Y	?	Y	Y	?	?	Y	Y	?	?	?
n=6	Y	Y	Y	Y	Y	N	Y	Y	?	N	Y	Y	?	?	?, N ∀m =6+4k
...	Y	Y	Y	Y	Y	?	Y	Y	?	?	Y	Y	?	?	?
comments	stars Y	Y	Y	Y	Y ∀n > 0	? N ∀n even	Y	Y	?	? N ∀n even	Y	Y	?	?	?

You'll notice that the only cases in the chart known to not be graceful are those corresponding to parity violations. Hence:

Conjecture (Brundage, 1994):

The generalized cone $C_m + \overline{K_n}$ is graceful except when one of the following holds:

1. $n=0$ and $m\equiv 1 \pmod{4}, m > 3$ or
2. $n$ is even and $m\equiv 2 \pmod{4}, m > 3$.

When I worked on this in 1994, only cycles, wheels, and cases failing the parity condition were known. Gallian's latest survey now says the following cases are known:

• $n \equiv 0 \pmod{2}, m \gt 2, m \equiv 2 \pmod{4}$ violate the parity condition and are not graceful. ^[1]
• (cycles) $n=0$ are graceful if and only if $m \equiv 0,3 \pmod{4}$ or $m < 3$. ^{[1:1] [2]}
• (wheels) $n=1, \forall m$ are graceful ^[3]
• $m \equiv 0,3 \pmod{12}, \forall n$ are graceful ^[4],($m=3$ also in ^[5])
• $m=4, \forall n$ are graceful ^{[4:1] [5:1]}
• $m=7, \forall n$ are graceful ^{[4:2] [5:2]}
• $m=9, n=2$ is graceful ^{[4:3] [5:3]}
• $m=11, \forall n$ are graceful ^[4:4]
• $m=19, \forall n$ are graceful ^[4:5]
• $m=2, n=3,4,5,7,8,9,11$ ^[6] ($n=3,5,7$ first shown in ^[4:6])

My novel results, presented here:

• $m=5, \forall n$ are graceful ^[5:4] ($n=2$ also in ^[4:7])
• $m=6, n=3$ is graceful ^[7]
• $m=8, \forall n$ are graceful ^[5:5]
• $m=9, n=3$ is graceful ^[7:1]

My 1994 Results

An example of a graceful labeling for Cone(4,2) is:

However, it's confusing to show all the lines between the cycle and the isolated points, so in the diagrams below I omit those edges, like this:

Here are my results from 1994, finally published here in 2014. I found constructive labelings for the cases $m=2,3,4,5,7,8, \forall n$.

Observe that the number of edges $E = m (n+1)$ except when $m=2$, in which case there are $E = 2n + 1$ edges. Also, observe that the cycle labeling could be rotated or flipped, and the other vertex labels permuted. I do not count those as separate labelings.

$m=2$

Label the cycle vertices $0,E$ and the other vertices $1, 2, \dots m$ to achieve a graceful labelling.

Proof:

The cycle vertices make the edge labeled $E$, and the other vertices make the edges labeled $1, 2, \dots m$ and $E-1, E-2, \dots E-m$. This labelling is graceful because $E-m = m+1$ and thus all edge labels in $[1,E]$ are achieved exactly once.

$m=3$

Label the cycle vertices $0, E-1, E$ and the other vertices $2, 5, 8, \dots, E-4$ to achieve a graceful labelling.

Proof:

The cycle vertices make the edges labeled $1, E-1, E$ and the other vertices make the edges labelled $2, 5, 8, \dots, E-4; E-3, E-6, E-9, \dots; 3; E-2, E-5, E-8, \dots, 4$. Each of these covers a different residue class $mod 3$ without duplicates, thus achieving every label exactly once.

$m=4$

Label the cycle vertices $0, E, E/2, 3E/4$ and the other vertices $1, 2, \dots, m$ to achieve a graceful labelling.

Proof:

The cycle vertices make the edges labeled $E, E/2, E/4, 3E/4$ and the other vertices make the edges whose labels cover each quarter of the labels without duplicates.

$m=5$

Label the cycle vertices $0, E, E-3, 3, E-1$ and the other vertices $2, 8, 13, 18, \dots, E-7$ to achieve a graceful labelling.

Proof:

The cycle vertices make the edges labeled $E, 3, E-6, E-4, E-1$ and the other vertices make the edges labeled $2, 8, 13, \dots, E-7; E-2, E-8, E-13, \dots, 7; E-5, E-11, E-16, \dots, 4; 1, 5, 12, \dots, E-10; E-3, E-9, E-14, \dots, 6$. These cover the residues mod 5 without duplicates.

$m=7$

Label the cycle vertices $0, E, 6, E-3, 5, E-2, E-1$ and the other vertices $2, 11, 18, 25, \dots, E-10$.

Proof:

The cycle vertices make the edges $E, E-6, E-9, E-8, E-7, 1, E-1$. The other vertices make the edges $2, 11, 18, \dots, E-10; E-2, E-11, E-18, \dots, 10; 4, 5, 12, \dots, E-16; E-5, E-14, E-21, \dots, 7; 3, 6, 13, \dots, E-15; E-4, E-13, E-20, \dots, 8; E-3, E-12, E-19, \dots, 9$, which cover the residues mod 7 without duplicates.

$m=8$

For $n=1$, label the cycle vertices $0, 15, 3, 1, 14, 13, 2, 16$ and the other vertex $6$.

For $n \ge 2$, label the cycle vertices $0, E, 2, 3, E-2, 1, E-3, E-1$ and the other vertices $6, 10, 14, \dots, E/2 - 2$.

Proof:

The cycle vertices make the edges $E, E-2, 1, E-5, E-3, E-4, 2, E-1$. The other vertices combine with 0, 1, 2, 3 to make edges that cover the residue classes $\mod 4$ up to $E/2 - 2$, and combine with the vertices $E-1, E-2, E-3, E$ to cover the other half of these residue classes, without overlap.

Note that the $n=1$ case is the same as the general case except that the $3$ and $E-3$ labels changed places.

My 2014 Results

While writing this up, I decided to explore some of the parts of the chart above that remained unknown. Here are some additional cases that are graceful.

• $m=6, n=3$. I found 4 graceful labelings up to symmetry:

  • Label the cycle vertices 0, 14, 2, 7, 5, 20 and the other vertices 13, 23, 24
  • Label the cycle vertices 0, 15, 2, 4, 7, 18 and the other vertices 14, 23, 24
  • Label the cycle vertices 4, 19, 17, 22, 10, 24 and the other vertices 0, 1, 11
  • Label the cycle vertices 6, 17, 20, 22, 9, 24 and the other vertices 0, 1, 10

• $m=9, n=3$. I found 3 graceful labelings up to symmetry:

  • Label the cycle vertices 0 35 34 17 33 15 21 32 36 and the other vertices 2 7 12
  • Label the cycle vertices 4 18 21 33 35 15 34 27 36 and the other vertices 0 5 10
  • Label the cycle vertices 15 3 35 27 14 33 34 16 36 and the other vertices 0 5 10

I also found no solutions for m=6, n=5 in an exhaustive search. I have not verified that this result is correct.

Perhaps I'll do more later.

Conclusion

The generalized cone graphs $\text{Cone}(m,n) = C_m + \overline{K_n}$ are graceful for $m=2,3,4,5,7,8, \forall n$; for $m=6,n=3$; for $m=9, n=3$; and all the other cases from the literature listed above.

I conjecture that $\text{Cone}(m,n)$ is graceful if and only if the parity condition holds. I.e., n is odd or n=0 and $m \equiv 0,3 \pmod{4}$ or $n \equiv 0 \pmod{2}$ and $m \equiv 0,1,3 \pmod{4}$.

Gracefully labeling generalized cones so far boils down to a lot of case analysis. A general solution for all $m, n$ remains elusive.

References

---

1. Theory of Graphs, Rosa, 1967. ↩︎ ↩︎

2. This is often mis-stated as just the congruence. But obviously, $C_1$ and $C_2$ are graceful, despite not satisfying the congruence. ↩︎

3. Labelling Prisms, Frucht & Gallian, 1988. ↩︎

4. Gracefulness of $C_{2x+1} \cup P_{x-2\theta}$, Bhat-Nayak & Selvam, 1996. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

5. Graceful labellings of cones, Brundage, 1994 (published 2014). ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

6. Graceful graphs and graceful labelings, Redl, 2003. ↩︎

7. Graceful labellings of cones, Brundage, 2014. ↩︎ ↩︎