The complete-partite graph cycle-space conjecture for K^{s,s-1}

Let Ks^,s1\mathrm{K}^{\widehat{s},s-1} denote the graph described in the paper, and let Z1(Ks^,s1;F2)\mathrm{Z}_1(\mathrm{K}^{\widehat{s},s-1};\mathbb{F}_2) be its cycle space over F2\mathbb{F}_2. Let H(Ks^,s1)\mathcal{H}(\mathrm{K}^{\widehat{s},s-1}) denote the set of Hamilton circuits of this graph, and let H(Ks^,s1)F2\langle\mathcal{H}(\mathrm{K}^{\widehat{s},s-1})\rangle_{\mathbb{F}_2} be their F2\mathbb{F}_2-linear span.

The complete-partite graph cycle-space conjecture. For every s4s\geq 4,

Z1(Ks^,s1;F2)=H(Ks^,s1)F2.\mathrm{Z}_1(\mathrm{K}^{\widehat{s},s-1};\mathbb{F}_2) = \langle\mathcal{H}(\mathrm{K}^{\widehat{s},s-1})\rangle_{\mathbb{F}_2}.

The claim would provide an infinite family of graphs with a degree-22 vertex in which every cycle is a symmetric difference of Hamilton circuits, showing that the corresponding implication in the paper does not hold without additional hypotheses. The source presents this as seeming to hold based on examples and calculations, rather than as an established result.

Sources & referencesView supporting material

Primary source

Peter C. Heinig, “When Hamilton circuits generate the cycle space of a random graph”, arXiv:1303.0026 (2013).

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.