On the connectivity of -diamond-free graphs

For a vertex v of a graph G , we denote by d ( v ) the degree of v . The local connectivity κ ( u , v ) of two vertices u and v in a graph G is the maximum number of internally disjoint u – v paths in G , and the connectivity of G is defined as κ ( G ) = min { κ ( u , v ) | u , v ∈ V ( G ) } . Clearly, κ ( u , v ) ≤ min { d ( u ) , d ( v ) } for all pairs u and v of vertices in G . Let δ ( G ) be the minimum degree of G . We call a graph G maximally connected when κ ( G ) = δ ( G ) and maximally local connected when κ ( u , v ) = min { d ( u ) , d ( v ) } for all pairs u and v of distinct vertices in G . integer p ≥ 2 , we define a p -diamond as the graph with p + 2 vertices, where two adjacent vertices have exactly p common neighbors, and the graph contains no further edges. For p = 2 , the 2-diamond is the usual diamond. We call a graph p -diamond-free if it contains no p -diamond as a (not necessarily induced) subgraph. 7, Dankelmann, Hellwig and Volkmann [P. Dankelmann, A. Hellwig, L. Volkmann, On the connectivity of diamond-free graphs, Discrete Appl. Math. 155 (2007), 2111–2117] proved that a connected diamond-free graph G of order n ≤ 3 δ ( G ) is maximally connected when δ ( G ) ≥ 3 . In this paper, we show that such graphs are even maximally local connected when n ≤ 3 δ ( G ) − 1 . Examples demonstrate that this bound is best possible. In addition, we present similar results for p -diamond-free graphs.