math.CO — Combinatorics

Tools for proving that graphs are not graceful

Contributed by Boon Suan Ho

A graph with $m$ edges is graceful if its vertices can be labeled with distinct integers in $[0,m]$ whose edge differences are exactly $1,\dots,m$. Graceful labelings have been constructed for sixty years, but there are few general methods for showing that a graph is not graceful. We start from a single generating-function identity that restates gracefulness, and derive three tools from it: residues at roots of unity, extending the classical parity condition; positivity on the unit circle, whose semidefinite form amounts exactly to the Goemans–Williamson max-cut relaxation tested against the minimum of the Dirichlet kernel; and the label interval itself, which forces the labels of a dense subgraph to have a large span. The consequences include new families of ungraceful graphs: every edge-transitive graph that contains $K_6$, the Paley graphs $P(q)$ with $q\ge37$, the Kneser graphs $K(n,k)$ with $n\ge5.61k$, almost every $d$-regular graph with $d\ge84$, and the polarity graphs $\mathrm{ER}_q$ with $q\ge23$, which contain no $4$-cycle. For the semidefinite form of positivity we also determine exactly what it can prove, and we show that a planar refinement is strictly stronger: it excludes the Kneser graph $K(11,2)$ with any seven edges deleted.