Edge-size conjecture for graceful zillion graphs

About 6 years old · traced to

Let Γ\Gamma be a zillion graph with ω\omega odd cycles and μ\mu even cycles, and let ∣E(Γ)∣|E(\Gamma)| denote its number of edges. Edge-size conjecture. There exist a quadratic polynomial f∈Z[x]f\in\mathbb{Z}[x] and a linear polynomial g∈Z[x]g\in\mathbb{Z}[x] such that Γ\Gamma is graceful whenever

∣E(Γ)∣≥f(ω)+g(μ).|E(\Gamma)|\geq f(\omega)+g(\mu).

Kotzig's lower bound, as adapted in the source, shows that a zillion graph with ω\omega odd cycles must satisfy a quadratic lower bound in its number of edges for gracefulness. The proposed conjecture gives a quadratic contribution from odd cycles and a linear contribution from even cycles, and remains open.

References

Primary source

A. C. Burgess, P. Danziger and T. Traetta, “On the Oberwolfach problem for single-flip 2-factors via graceful labelings”, arXiv:2010.07231 (2020).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.