Super-connected arc-transitive digraphs

被引:6
作者
Meng, Jixiang [1 ]
Zhang, Zhao [1 ]
机构
[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China
关键词
Super-connected; Hyper-connected; Vosperian; Bi-super-connected; Arc-transitive; Oriented graph; EDGE-CONNECTIVITY; GRAPHS; VERTEX;
D O I
10.1016/j.dam.2008.08.018
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A digraph is said to be super-connected if every minimum vertex cut is the out-neighbor set or in-neighbor set of a vertex. A digraph is said to be reducible, if there are two vertices with the same out-neighbor set or the same in-neighbor set. In this paper, we prove that a strongly connected arc-transitive oriented graph is either reducible or super-connected. Furthermore, if this digraph is also an Abelian Cayley digraph, then it is super-connected. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:653 / 658
页数:6
相关论文
共 20 条
[1]   Extraconnectivity of s-geodetic digraphs and graphs [J].
Balbuena, C .
DISCRETE MATHEMATICS, 1999, 195 (1-3) :39-52
[2]   SYNTHESIS OF RELIABLE NETWORKS - A SURVEY [J].
BOESCH, FT .
IEEE TRANSACTIONS ON RELIABILITY, 1986, 35 (03) :240-246
[3]  
Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[4]   THE CONNECTIVITY OF LARGE DIGRAPHS AND GRAPHS [J].
FIOL, MA .
JOURNAL OF GRAPH THEORY, 1993, 17 (01) :31-45
[5]   VERTEX TRANSITIVITY AND SUPER LINE CONNECTEDNESS [J].
HAMIDOUNE, YO ;
TINDELL, R .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (04) :524-530
[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]   VOSPERIAN AND SUPERCONNECTED ABELIAN CAYLEY DIGRAPHS [J].
HAMIDOUNE, YO ;
LLADO, AS ;
SERRA, O .
GRAPHS AND COMBINATORICS, 1991, 7 (02) :143-152
[8]   CONNECTIVITY PROBLEMS IN ORIENTED GRAPHS [J].
HAMIDOUNE, YO .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1981, 30 (01) :1-10
[9]   CONDITIONAL CONNECTIVITY [J].
HARARY, F .
NETWORKS, 1983, 13 (03) :347-357
[10]  
Li QL, 1999, NETWORKS, V33, P157, DOI 10.1002/(SICI)1097-0037(199903)33:2<157::AID-NET6>3.0.CO