On the generalized (edge-)connectivity of graphs ∗
Xueliang Li, Yaping Mao, Yuefang Sun · Australas. J Comb. · 2014
The generalized k-connectivity κk(G) of a graph G was introduced by Chartrand et al. in 1984. It is natural to introduce the concept of gener- alized k-edge-connectivity, λk(G). For general k, the generalized k-edge- connectivity of a complete graph is obtained. For k ≥ 3, tight upper and lower bounds of κk(G )a ndλk(G) are given for a connected graph G of order n ,n amely, 1≤ κk(G) ≤ n −� kand 1 ≤ λk(G) ≤ n −� k � .M ore- over, graphs of order n such that κk(G )= n −� kand λk(G )= n −� k � are characterized. Nordhaus-Gaddum-type results for the generalized k- connectivity are also obtained. For k = 3, we study the relation between the edge-connectivity and the generalized 3-edge-connectivity of a graph. Upper and lower bounds of λ3(G )f or ag raphG in terms of the edge- connectivity λ of G are obtained, that is, 3λ−2 4 ≤ λ3(G) ≤ λ ,a nd two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain λ(G) − 1 ≤ λ3(G) ≤ λ(G )i fG is a connected planar graph, and we also obtain the relation between the generalized 3-connectivity and generalized 3-edge-connectivity of a graph and its line graph.