No label defined (Q4940091)

The authors generalize Ollmann's results by proving that any \(n\)-node \(P_3\)-connected graph has at least \({3\over 2} n - 3\) edges. They also describe the set of all \(P_3\)-connected graphs with \(\lceil {3\over 2} n \rceil - 3\) edges. This is a superset of Ollmann's set. 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 \({3\over 2} n - 3\) edges. He also described the set of all \(C_4\)-saturated graphs with \(\lceil {3\over 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.