On the generalized (edge-)connectivity of graphs

Abstract

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\ge 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\le {\kappa }_k(G)\le n-\lceil \frac{k}{2}\rceil$ and $1\le {\lambda }_k(G)\le 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}\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\le {\lambda }_3(G)\le \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.

15 pages

References in corpus (1)

• The minimal size of a graph with generalized connectivity ${\kappa }_3=2$

Cited by in corpus (13)

• A survey on the generalized connectivity of graphs
• The generalized 3-connectivity of random graphs
• On the pedant tree-connectivity of graphs
• Graphs with large generalized (edge-)connectivity
• Further hardness results on the generalized connectivity of graphs
• Strong Subgraph Connectivity of Digraphs: A Survey
• $k$-tree connectivity of line graphs
• The generalized 3-(edge) connectivity of total graphs
• Path connectivity of line graphs
• Extremality and Sharp Bounds for the $k$-edge-connectivity of Graphs
• Constructing Internally Disjoint Pendant Steiner Trees in Cartesian Product Networks
• Two bounds for generalized $3$-connectivity of Cartesian product graphs
• Extremal results for directed tree connectivity