Super-connected edge transitive graphs

被引:8
作者
Zhang, Zhao [1 ,2 ]
Meng, Jixiang [1 ]
机构
[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China
[2] Zhengzhou Univ, Dept Math, Zhengzhou 450052, Peoples R China
基金
中国国家自然科学基金;
关键词
super-connected; edge transitive; reducible;
D O I
10.1016/j.dam.2007.09.014
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A graph G is said to be super-connected if any minimum cut of G isolates a vertex. In a previous work due to the second author of this note, super-connected graphs which are both vertex transitive and edge transitive are characterized. In this note, we generalize the characterization to edge transitive graphs which are not necessarily vertex transitive, showing that the only irreducible edge transitive graphs which are not super-connected are the cycles C-n (n >= 6) and the line graph of the 3-cube, where irreducible means the graph has no vertices with the same neighbor set. Furthermore, we give some sufficient conditions for reducible edge transitive graphs to be super-connected. (C) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码:1948 / 1953
页数:6
相关论文
共 11 条
[1]   On the restricted connectivity and superconnectivity in graphs with given girth [J].
Balbuena, C. ;
Cera, M. ;
Dianez, A. ;
Garcia-Vazquez, P. ;
Marcote, X. .
DISCRETE MATHEMATICS, 2007, 307 (06) :659-667
[2]  
BIGGS N, 1993, ALGEBRAIC GRAPH THEO, P115
[4]   On the extraconnectivity of graphs [J].
Fabrega, J ;
Fiol, MA .
DISCRETE MATHEMATICS, 1996, 155 (1-3) :49-57
[5]   THE SUPERCONNECTIVITY OF LARGE DIGRAPHS AND GRAPHS [J].
FIOL, MA .
DISCRETE MATHEMATICS, 1994, 124 (1-3) :67-78
[6]   Subsets with small sums in Abelian groups' .1. The Vosper property [J].
Hamidoune, YO .
EUROPEAN JOURNAL OF COMBINATORICS, 1997, 18 (05) :541-556
[7]   CONDITIONAL CONNECTIVITY [J].
HARARY, F .
NETWORKS, 1983, 13 (03) :347-357
[8]   MINIMAL EDGE-N-CONNECTED GRAPHS [J].
MADER, W .
MATHEMATISCHE ANNALEN, 1971, 191 (01) :21-&
[9]   Connectivity of vertex and edge transitive graphs [J].
Meng, JX .
DISCRETE APPLIED MATHEMATICS, 2003, 127 (03) :601-613
[10]  
Tindell R, 1996, COMBINATORIAL NETWOR, P41