# Do the windmills $K_5^{(3)}$ and $K_5^{(4)}$ admit graceful labellings?

Here $$K_n^{(k)}$$ is the windmill formed by taking $$k$$ copies of $$K_n$$ and gluing them at a vertex. A graceful labelling of a graph $$G=(V,E)$$ is a vertex labelling $$f:V \rightarrow \{0,\ldots,|E|\}$$ such that different vertices get different labels and $$|f(i)-f(j)|$$ is distinct for distinct edges $$\{i,j\}$$. For example this is a graceful labelling of $$K_3^{(4)}$$ I drew by hand: $K_3^{(4)}$." />

Most of the time, windmills cannot be gracefully labelled:

A necessary condition for $$K_n^{(k)}$$ to be graceful is that $$n \leq 5$$.
Gallian, A Dynamic Survey of Graph Labeling, Electron. J. Combin., 2017+.

I searched the literature and found a gajillion papers on the topic, within which I found:

k=1 k=2 k=3 k=4
n=2
n=3 ✗ (Graham, Sloane, pdf) ✗ (Bermond, Kotzig, Turgeon, pdf) ✓ (see above)
n=4 ✗ (Graham, Sloane, pdf) ✗ (Bermond, Kotzig, Turgeon, pdf) ✓ (Bermond, pdf; image)
n=5 ✗ (Graham, Sloane, pdf) ? ?

When $$n=2$$, we have a star, and that's easy (put a zero in the middle). When $$k=1$$, we have a complete graph, and there's a bunch of references in the Gallian survey.

I didn't find answers for $$K_5^{(3)}$$ and $$K_5^{(4)}$$. I'm expecting this to be in the literature (or maybe on someone's computer).

Question: Do the windmills $$K_5^{(3)}$$ and $$K_5^{(4)}$$ admit graceful labellings?

I whipped up some GAP code (and an improved version); it was able to confirm the known results, but it's too slow for $$K_5^{(3)}$$ and $$K_5^{(4)}$$. It found graceful labellings of $$K_3^{(5)}$$ and $$K_4^{(5)}$$ though: $K_3^{(5)}$." /> $K_4^{(5)}$." />

• My brute-force wasn't able to find a labelling for any of the two. Jun 14 at 12:05
• I'd expect that a SAT solver should be able to confirm the nonexistence of a graceful labeling in these two cases. Introduce Boolean variables $x_{ij}$ to indicate that vertex $i$ gets label $j$ and Boolean variables $y_{ij}$ to indicate that edge $i$ gets label $j$. It is not hard to write down all the necessary constraints as SAT clauses. I'd also recommend adding a few symmetry-breaking constraints to speed up the computation. Jun 15 at 1:10
• My little C program says that neither $K_5^{(3)}$ nor $K_5^{(4)}$ have graceful labellings. It took 3 seconds and 4 minutes, respectively. This confirms Mikhail's result so I think this is sufficient verification. Jun 15 at 5:09
• @BrendanMcKay By Bosák's result in my answer, $K_5^{(2j+1)}$ for $j\ge0$ is ungraceful. Jun 15 at 5:42
• @hoboonsuan Thanks, that saves me some computing time. I have $K_5^{(4)}$ down to 20 seconds and wonder if $K_5^{(6)}$ is plausible. Jun 15 at 6:25

A partial answer: a result of Juraj Bosák says that if all vertices of a graceful graph have even degree, then the graph has $$4k$$ or $$4k+3$$ edges for some integer $$k$$ (proof given below).

Since $$K_5^{(3)}$$ has $$30$$ edges, it is ungraceful.

Gallian's survey attributes this result to [Rosa 1967]. See also Don Knuth's work-in-progress section 7.2.2.3 of The Art of Computer Programming (https://www-cs-faculty.stanford.edu/~knuth/fasc7a.ps.gz) for a computational discussion graceful labelings as constraint satisfaction problems.

Lemma 7.2.2.3O from The Art of Computer Programming. In any graceful labeling of a graph with $$4k+1$$ or $$4k+2$$ edges, the number of vertices with an odd degree and an odd label is always odd.

Proof. We have $$\sum_{uv\in E(G)}|l(u)-l(v)|=1+2+\dots+m=\binom{m+1}{2}$$ when there are $$m$$ edges; and a given vertex $$v$$ appears exactly $$\deg(v)$$ times in this sum. Working modulo $$2$$, we also have $$|l(u)-l(v)|\equiv l(u)+l(v)$$. Therefore $$\sum_v\deg(v)l(v)\equiv\binom{m+1}{2}$$. But $$\binom{m+1}{2}\equiv1$$ when $$m=4k+1$$ or $$m=4k+2$$. $$\square$$

### Overview: gracefulness of windmill graphs $$K_n^{(j)}$$

$$n$$ $$\backslash$$ $$j$$ $$1$$ $$2$$ $$3$$ $$4$$ $$5$$ $$6$$ $$7$$ $$j\ge8$$
$$2$$
$$3$$ ✓ if and only if $$j\equiv0\hbox{ or }1\pmod4$$
$$4$$ ✓ if $$j\le1000$$; ? otherwise
$$5$$ ? ✗ if $$j$$ is odd; ? if $$j$$ is even
$$n\ge6$$

When $$n=2$$, $$K_2^{(j)}=K_{1,j}$$ is a star and can always be gracefully labeled by placing $$0$$ in the internal vertex.

When $$n=3$$, $$K_3^{(j)}$$ is a friendship graph and is graceful if and only if $$j\equiv0\hbox{ or }1\pmod4$$. The forward implication follows from J. Bosák's result in [Rosa 1965], and the reverse implication follows from a construction of [Skolem 1957].

When $$n=4$$ and $$4\le j\le1000$$, $$K_n^{(j)}$$ is graceful due to a construction of [Ge et al. 2010] (they construct $$(12j+1,4,1)$$-perfect distance families for $$4\le j\le1000$$, which are equivalent to graceful labelings of $$K_4^{(j)}$$). When $$j>1000$$, nothing is known, though [Bermond 1979] conjectures that $$K_4^{(j)}$$ is graceful for $$j\ge4$$.

When $$n=5$$, if $$j$$ is odd, Bosák's result implies that $$K_5^{(j)}$$ is ungraceful. For even $$j\ge6$$, nothing is known.

When $$n\ge6$$, a result of [Koh et al. 1980] implies that $$K_n^{(j)}$$ is always ungraceful.

### References

[Skolem 1957] Thoralf A. Skolem, On Certain Distributions of Integers In Pairs With Given Differences. Mathematica Scandinavica 5 (1957), 57–68. https://doi.org/10.7146/math.scand.a-10490

[Rosa 1965] Alexander Rosa, O Cyklických Rozkladoch Kompletného Grafu, Kandidátska dizertačná práca. (Bratislava: Českoslovanská akadémia vied, November 1965), ii+86 pages. (Note: Rosa attributes the result above to J. Bosák on page 17). https://archive.org/details/o-cyklickych-rozkladoch-kompletneho-garfu

[Rosa 1967] Alexander Rosa, On certain valuations of the vertices of a graph. Theory of Graphs (International Symposium, Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris (1967), 349–355. https://www.researchgate.net/publication/244474213_On_certain_valuations_of_the_vertices_of_a_graph

[Bermond 1979] Jean-Claude Bermond, Graceful graphs, radio antennae and French windmills. In Graph Theory and Combinatorics (ed. R. J. Wilson), Research Notes in Mathematics 34 (1979), 18–37. (Proceedings of a one-day conference in combinatorics and graph theory held at the Open University, England, on 12 May 1978.) https://hal.inria.fr/hal-02340680

[Koh et al. 1980] Khee Meng Koh, D. G. Rogers, H. K. Teo, and K. Y. Yap, Graceful graphs: some further results and problems. Congressus Numerantium 29: Proceedings of the 11th Southeastern Conference on Combinatorics, Graph Theory, and Computing, Winnipeg, Manitoba (December 1980), 559–571

[Ge et al. 2010] Gennian Ge, Ying Miao, and Xianwei Sun, Perfect difference families, perfect difference matrices and related combinatorial structures. Journal of Combinatorial Designs 18(6) (2010), 415–449. https://doi.org/10.1002/jcd.20259

[Knuth 2021] Donald E. Knuth, The Art of Computer Programming Volume 4 Pre-Fascicle 7A, Section 7.2.2.3: Constraint Satisfaction (2020–). https://www-cs-faculty.stanford.edu/~knuth/fasc7a.ps.gz