Bondy's conjecture on long circuits generating the cycle space

Let dZd\in\mathbb{Z}, let XX be a vertex-3-connected graph with f0(X)f_0(X) vertices, and let δ(X)\delta(X) be its minimum degree. Write Z1(X;Z/2)\mathrm{Z}_1(X;\mathbb{Z}/2) for the cycle space of XX over Z/2\mathbb{Z}/2.

Bondy's conjecture. If

f0(X)2dandδ(X)d,f_0(X)\geq 2d\qquad\text{and}\qquad \delta(X)\geq d,

then the set of all circuits of length at least 2d12d-1 is a Z/2\mathbb{Z}/2-generating system of Z1(X;Z/2)\mathrm{Z}_1(X;\mathbb{Z}/2).

The conjecture proposes that sufficiently long circuits generate the entire cycle space of a sufficiently dense, vertex-3-connected graph. The source notes that Locke proved it under the additional assumption that XX is non-Hamiltonian or f0(X)4d5f_0(X)\geq 4d-5; the general statement remains open.

Sources & referencesView supporting material

Primary source

Peter C. Heinig, “On prisms, Möbius ladders and the cycle space of dense graphs”, arXiv:1112.5101 (2011).

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.