Number of Edges in 3-Connected Graphs with Cyclic Neighborhoods
By: Samuel Schneider, Torsten Ueckerdt
Potential Business Impact:
Finds hidden patterns in connected things.
Chernyshev, Rauch and Rautenbach [Discrete Math., 2025] introduce forest cuts, i.e., vertex separators that induce a forest. They conjecture that, similar to a result by Chen and Yu [Discrete Math., 2002], every $n$-vertex graph with less than $3n-6$ edges has a forest cut. As an intermediate goal they ask how many edges an $n$-vertex $3$-connected graph must have such that the neighborhood of every vertex contains a cycle. Li, Tang and Zhan [arXiv, 2024] resolve this problem by showing that every such graph has at least $15n/8$ edges, while there are examples of such graphs with exactly $15n/8$ edges. We give a much shorter proof for this.
Similar Papers
On an Erdős--Lov'asz problem: 3-critical 3-graphs of minimum degree 7
Discrete Mathematics
Finds new math rules for tricky shapes.
Isolation of non-triangle cycles in graphs
Combinatorics
Finds small groups of points to break all cycles.
Cops and Robbers, Clique Covers, and Induced Cycles
Combinatorics
Finds how many cops catch a robber on a map.