On the connectivity of pp-diamond-free graphs

For a vertex vv of a graph GG, we denote by d(v)d(v) the degree   of vv. The local connectivity  κ(u,v)κ(u,v) of two vertices uu and vv in a graph GG is the maximum number of internally disjoint u–vu–v paths in GG, and the connectivity   of GG is defined as κ(G)=min{κ(u,v)|u,v∈V(G)}. Clearly, κ(u,v)≤min{d(u),d(v)}κ(u,v)≤min{d(u),d(v)} for all pairs uu and vv of vertices in GG. Let δ(G)δ(G) be the minimum degree of GG. We call a graph GGmaximally connected   when κ(G)=δ(G)κ(G)=δ(G) and maximally local connected when κ(u,v)=min{d(u),d(v)}κ(u,v)=min{d(u),d(v)} for all pairs uu and vv of distinct vertices in GG.For an integer p≥2p≥2, we define a pp-diamond   as the graph with p+2p+2 vertices, where two adjacent vertices have exactly pp common neighbors, and the graph contains no further edges. For p=2p=2, the 2-diamond is the usual diamond. We call a graph pp-diamond-free   if it contains no pp-diamond as a (not necessarily induced) subgraph.In 2007, 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 GG of order n≤3δ(G)n≤3δ(G) is maximally connected when δ(G)≥3δ(G)≥3. In this paper, we show that such graphs are even maximally local connected when n≤3δ(G)−1n≤3δ(G)−1. Examples demonstrate that this bound is best possible. In addition, we present similar results for pp-diamond-free graphs.