Here are my results, conjecture, 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

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 (the starred results are presented here for the first time):

• \(n \equiv 0 \pmod{2}, m > 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, 2]
• (wheels) \(n=1, \forall m\) are graceful [3]
• \(m \equiv 0,3 \pmod{12}, \forall n\) are graceful [4, \(m=3\) also in 6]
• \(m=4, \forall n\) are graceful [4, 6]
• \(m=5, \forall n\) are graceful [6, \(n=2\) also in 4]
• \(m=6, n=3\) is graceful [7]
• \(m=7, \forall n\) are graceful [4, 6]
• \(m=8, \forall n\) are graceful [6]
• \(m=9, n=2\) is graceful [4, 6]
• \(m=9, n=3\) is graceful [7]
• \(m=11, \forall n\) are graceful [4]
• \(m=19, \forall n\) are graceful [4]
• \(m=2, n=3,4,5,7,8,9,11\) [5, \(n=3,5,7\) first shown in 4]

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 graphs and graceful labelings (Redl, 2003)
6. Graceful labellings of cones (Brundage, 1994, published 2014)
7. Graceful labellings of cones (Brundage, 2014)

You’ll notice that the only cases in the chart with ‘N’ in are those corresponding to parity violations. In 1994, I conjectured:

and it’s held up for 20 years (so far).

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.

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.

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.

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.

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\).

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\).

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 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 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.