Article ID Journal Published Year Pages File Type
1709435 Applied Mathematics Letters 2008 4 Pages PDF
Abstract

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 κ(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)} 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 n(G)≤δ(G)⋅2p−12p−3. As an extension of this result, we will show in this work that these conditions even guarantee that GG is maximally locally connected.

Related Topics
Physical Sciences and Engineering Engineering Computational Mechanics
Authors
,