Super-connected but not super edge-connected graphs |
| |
Authors: | Jin-Xin Zhou Yan-Quan Feng |
| |
Affiliation: | Department of Mathematics, Beijing Jiaotong University, Beijing 100044, PR China |
| |
Abstract: | A connected graph G is super-connected (resp. super edge-connected) if every minimum vertex-cut (resp. edge-cut) isolates a vertex of G. In Super connectivity of line graphs, Inform. Process. Lett. 94 (2005) 191-195], Xu et al. shows that a super-connected graph with minimum degree at least 4 is also super edge-connected. In this paper, a characterization of all super-connected but not super edge-connected graphs is given. It follows from this result that there is a unique super-connected but not super edge-connected graph with minimum degree 3, that is, the Ladder graph L3 of order 6, and that there are infinitely many super-connected but not super edge-connected graphs with minimum degree 1 or 2. |
| |
Keywords: | Interconnection networks Connectivity Super-κ Super-λ |
本文献已被 ScienceDirect 等数据库收录! |
|