On the generalized (edge-)connectivity of graphs

Abstract

The generalized $k$-connectivity $\hat{I}{º}_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 $\hat{I}{»}_k(G)$. For general $k$, the generalized $k$-edge-connectivity of a complete graph is obtained. For $k\ge 3$, tight upper and lower bounds of $\hat{I}{º}_k(G)$ and $\hat{I}{»}_k(G)$ are given for a connected graph $G$ of order $n$, that is, $1\le \hat{I}{º}_k(G)\le n-\lceil \frac{k}{2}\rceil$ and $1\le \hat{I}{»}_k(G)\le n-\lceil \frac{k}{2}\rceil$. Graphs of order $n$ such that $\hat{I}{º}_k(G)=n-\lceil \frac{k}{2}\rceil$ and $\hat{I}{»}_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 $\hat{I}{»}_3(G)$ for a graph $G$ in terms of the edge-connectivity $\hat{I}»$ of $G$ are obtained, that is, $\frac{3\hat{I}»-2}{4}\le \hat{I}{»}_3(G)\le \hat{I}»$, and two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain that $\hat{I}»(G)-1\le \hat{I}{»}_3(G)\le \hat{I}»(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.

15 pages