On the generalized (edge-)connectivity of graphs

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$,tightupperandlowerboundsof$\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$\mathrm{.}Graphsoforder$n$suchthat$\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}\le {\lambda }_3(G)\le \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.