13
$\begingroup$

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:

A graceful labelling of <span class=$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:

A graceful labelling of <span class=$K_3^{(5)}$." />

A graceful labelling of <span class=$K_4^{(5)}$." />

$\endgroup$
6
  • 3
    $\begingroup$ My brute-force wasn't able to find a labelling for any of the two. $\endgroup$ Jun 14 at 12:05
  • $\begingroup$ 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. $\endgroup$ Jun 15 at 1:10
  • $\begingroup$ 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. $\endgroup$ Jun 15 at 5:09
  • 1
    $\begingroup$ @BrendanMcKay By Bosák's result in my answer, $K_5^{(2j+1)}$ for $j\ge0$ is ungraceful. $\endgroup$ Jun 15 at 5:42
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 15 at 6:25

1 Answer 1

7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.