Minimum-size conjecture for 3-connected graphs with cyclic neighborhoods
Minimum-size conjecture for 3-connected graphs with cyclic neighborhoods
Let be a graph of order and size . Assume that is 3-connected and that every neighborhood of a vertex contains a cycle. Minimum-size conjecture. Then
The question concerns graphs with no forest cut: such graphs are necessarily 3-connected and have a cycle in every vertex neighborhood. The family described in the paper has vertices and edges and satisfies these structural conditions, motivating the proposed lower bound; whether any such graph can have fewer edges remains open.
Sources & referencesView supporting material
Primary source
Vsevolod Chernyshev, Johannes Rauch and Dieter Rautenbach, “Forest Cuts in Sparse Graphs”, arXiv:2409.17724 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.