On local connectivity of graphs Original Research Article

The local connectivityκ(u,v)κ(u,v) of two vertices uu and vv in a graph GG is the maximum number of internally disjoint uu–vv paths in GG, and the connectivity of GG is defined as View the MathML sourceκ(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 locally connected when κ(u,v)=min{d(u),d(v)}κ(u,v)=min{d(u),d(v)} Turn MathJax on for all pairs uu and vv of vertices in GG. In 1993, Topp and Volkmann [J. Topp, L. Volkmann, Sufficient conditions for equality of connectivity and minimum degree of a graph, J. Graph Theory 17 (1993) 695–700] proved that a pp-partite graph of order n(G)n(G) is maximally connected when View the MathML sourcen(G)≤δ(G)⋅2p−12p−3. Turn MathJax on As an extension of this result, we will show in this work that these conditions even guarantee that GG is maximally locally connected.