Vulnerability of super edge-connected graphsReport as inadecuate

 Vulnerability of super edge-connected graphs

Vulnerability of super edge-connected 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: Vulnerability of super edge-connected graphs
A subset $F$ of edges in a connected graph $G$ is a $h$-extra edge-cut if $G-F$ is disconnected and every component has more than $h$ vertices. The $h$-extra edge-connectivity $\la^{h}G$ of $G$ is defined as the minimum cardinality over all $h$-extra edge-cuts of $G$. A graph $G$, if $\la^{h}G$ exists, is super-$\la^{h}$ if every minimum $h$-extra edge-cut of $G$ isolates at least one connected subgraph of order $h+1$. The persistence $ ho^{h}G$ of a super-$\la^{h}$ graph $G$ is the maximum integer $m$ for which $G-F$ is still super-$\la^{h}$ for any set $F\subseteq EG$ with $|F|\leqslant m$. Hong {\it et al.} Discrete Appl. Math. 160 2012, 579-587 showed that $\min\{\la^{1}G-\deltaG-1,\deltaG-1\}\leqslant ho^{0}G\leqslant \deltaG-1$, where $\deltaG$ is the minimum vertex-degree of $G$. This paper shows that $\min\{\la^{2}G-\xiG-1,\deltaG-1\}\leqslant ho^{1}G\leqslant \deltaG-1$, where $\xiG$ is the minimum edge-degree of $G$. In particular, for a $k$-regular super-$\la$ graph $G$, $ ho^{1}G=k-1$ if $\la^{2}G$ does not exist or $G$ is super-$\la^{2}$ and triangle-free, from which the exact values of $ ho^{1}G$ are determined for some well-known networks.

Author: Zhen-Mu Hong; Jun-Ming Xu


Related documents