On the connectivity of diamond-free graphs (Q2384395): Difference between revisions

In the paper are presented lower bounds on the connectivity of some special classes of graphs. A diamond is a graph on four vertices with five edges. Graph \(G\) is diamond-free if it does not contain a diamond as a subgraph. Let the order of \(G\) be \(n(G)\), the minimum degree \(\delta (G)\) and the vertex connectivity \(k(G)\). It is proved that if \(G\) is a connected diamond-free graph with \(\delta (G) \geq 3\), then \(k(G) \geq 4 \delta (G) - n(G)\). Another class of graphs considered in the paper is the class of \(C_4 \)-free graphs, where \(C_4\) is a cycle on 4 vertices. The authors prove that if \(G\) is a connected \(C_4\)-free graph with \(\delta (G) \geq 2\) and \(k(G)<\delta (G) \), then \(k(G) \geq 2 \delta (G)^2 - 2\delta (G)+2 - n(G)\) if \(\delta(G)\) is even, and \(k(G) \geq 2 \delta (G)^2 - 2\delta (G)+4 - n(G)\) if \(\delta(G)\) is odd.