On the generalized (edge-)connectivity of graphs

Xueliang Li, Yaping Mao, Yuefang Sun

Published 2011-12-01, updated 2013-05-14Version 3

The generalized $k$-connectivity $\kappa_k(G)$ of a graph $G$ was introduced by Chartrand et al. in 1984. It is natural to introduce the concept of generalized $k$-edge-connectivity $\lambda_k(G)$. For general $k$, the generalized $k$-edge-connectivity of a complete graph is obtained. For $k\geq 3$, tight upper and lower bounds of $\kappa_k(G)$ and $\lambda_k(G)$ are given for a connected graph $G$ of order $n$, that is, $1\leq \kappa_k(G)\leq n-\lceil\frac{k}{2}\rceil$ and $1\leq \lambda_k(G)\leq n-\lceil\frac{k}{2}\rceil$. Graphs of order $n$ such that $\kappa_k(G)=n-\lceil\frac{k}{2}\rceil$ and $\lambda_k(G)=n-\lceil\frac{k}{2}\rceil$ are characterized, respectively. 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 $\lambda_3(G)$ for a graph $G$ in terms of the edge-connectivity $\lambda$ of $G$ are obtained, that is, $\frac{3\lambda-2}{4}\leq \lambda_3(G)\leq \lambda$, and two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain that $\lambda(G)-1\leq \lambda_3(G)\leq \lambda(G)$ if $G$ is a connected planar graph, and the relation between the generalized 3-connectivity and generalized 3-edge-connectivity of a graph and its line graph.