On the generalized edge-connectivity of graphsReport as inadecuate



 On the generalized edge-connectivity of graphs


On the generalized edge-connectivity of graphs - Download this document for free, or read online. Document in PDF available to download.

Download or read this book online for free in PDF: On the generalized edge-connectivity of graphs
The generalized $k$-connectivity $\kappa kG$ 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 kG$. 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 kG$ and $\lambda kG$ are given for a connected graph $G$ of order $n$, that is, $1\leq \kappa kG\leq n-\lceil\frac{k}{2} ceil$ and $1\leq \lambda kG\leq n-\lceil\frac{k}{2} ceil$. Graphs of order $n$ such that $\kappa kG=n-\lceil\frac{k}{2} ceil$ and $\lambda kG=n-\lceil\frac{k}{2} ceil$ 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 3G$ for a graph $G$ in terms of the edge-connectivity $\lambda$ of $G$ are obtained, that is, $\frac{3\lambda-2}{4}\leq \lambda 3G\leq \lambda$, and two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain that $\lambdaG-1\leq \lambda 3G\leq \lambdaG$ 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.



Author: Xueliang Li; Yaping Mao; Yuefang Sun

Source: https://archive.org/







Related documents