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

Question

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)}$." />

Answer 1

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