Cyclic edge-connectivity conjecture for cages

A (k,g)(k,g)-cage is a smallest kk-regular graph of girth gg. A cycle-separating edge-cut is an edge-cut whose removal yields at least two components containing a cycle. A graph is cyclically rr-edge-connected if it has no cycle-separating edge-cut of fewer than rr edges.

Cyclic edge-connectivity conjecture. Every (k,g)(k,g)-cage is cyclically (k2)g(k-2)g-edge-connected.

The value (k2)g(k-2)g is a natural upper bound, obtained by separating a gg-cycle from the rest of the cage. The source presents this as an open conjecture and proposes it as the maximal possible cyclic edge-connectivity of cages.

Sources & referencesView supporting material

Primary source

Robert Lukoťka, Edita Máčajová and Jozef Rajník, “Cages and cyclic connectivity”, arXiv:2503.07400 (2025).

Additional references

2 papers in this index state this conjecture (2019–2025). The statement above is taken from the most recent of them; the others are arXiv:1902.10344.

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.