Minimum-size conjecture for 3-connected graphs with cyclic neighborhoods

About 2 years old · traced to

Let GG be a graph of order nn and size mm. Assume that GG is 3-connected and that every neighborhood of a vertex contains a cycle. Minimum-size conjecture. Then

m≥73(n−1).m\geq \frac{7}{3}(n-1).

The question concerns graphs with no forest cut: such graphs are necessarily 3-connected and have a cycle in every vertex neighborhood. The family GkG_k described in the paper has 3k+43k+4 vertices and 7k+77k+7 edges and satisfies these structural conditions, motivating the proposed lower bound; whether any such graph can have fewer edges remains open.

References

Primary source

Vsevolod Chernyshev, Johannes Rauch and Dieter Rautenbach, “Forest Cuts in Sparse Graphs”, arXiv:2409.17724 (2024).

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.