$P_3$-Connected Graphs of Minimum Size

Abstract

A graph without $4$-cycles is called $C_4$-free. A $C_4$-free graph is $C_4$-saturated if adding any edge creates a 4-cycle. Ollmann showed that any $n$-node $C_4$-saturated graph has at least $\frac{3}{2}n–3$ edges. He also described the set of all $n$-node $C_4$-saturated graphs with $\lceil \frac{3}{2}n\rceil –3$ edges. A graph is $P_3$-connected if each pair of nonadjacent nodes is connected by a path with exactly $3$ edges. A $C_4$-saturated graph is $P_3$-connected, but not vice versa. We generalize Ollmann’s results by proving that any $n$-node $P_3$-connected graph has at least $\frac{3}{2}n–3$ edges. We also describe the set of all $n$-node $P_3$-connected graphs with $\lceil \frac{3}{2}n\rceil –3$ edges. This is a superset of Ollmann’s set as some $n$-node $P_3$-connected graphs with $\lceil \frac{3}{2}n\rceil –3$ edges do have $4$-cycles.