Difference-set graceful-labeling conjecture for regular connected graphs

From papers

Let DD be a (v,k,μ)(v,k,\mu) difference set in a group GG, and define

λi=μigcd(k1,μ)\lambda_i=\frac{\mu i}{\gcd(k-1,\mu)}

for 1igcd(k1,μ)1\leq i\leq\gcd(k-1,\mu). A graph is DD-graceful when its vertices can be labeled by the elements of DD so that the differences associated with its edges are evenly distributed as required for a difference graph. Difference-set graceful-labeling conjecture. Every connected regular graph Γ\Gamma of order kk and degree

(k1)igcd(k1,μ)\frac{(k-1)i}{\gcd(k-1,\mu)}

is DD-graceful; consequently, there exists a (v,Γ,λi)(v,\Gamma,\lambda_i) difference graph with vertex set DD. The conjecture is motivated by the absence of counterexamples for regular connected graphs of order D|D|; the source records no general proof, although it notes later special cases for Paley difference sets and circulant graphs.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Marco Buratti, Anamari Nakic and Alfred Wassermann, “Graph decompositions in projective geometries”, arXiv:1907.03194 (2020).

Solutions 0

No solutions have been posted yet.