On the edge-connectivity of graphs with two orbits of the same size

被引：8

作者：

Yang, Weihua ^{[1
]}

Zhang, Zhao ^{[2
]}

Guo, Xiaofeng ^{[1
]}

Cheng, Eddie ^{[3
]}

Liptak, Laszlo ^{[3
]}

机构：

[1] Xiamen Univ, Sch Math Sci, Xiamen 361005, Fujian, Peoples R China

[2] Xinjiang Univ, Dept Math, Urumqi 830046, Peoples R China

[3] Oakland Univ, Dept Math & Stat, Rochester, MI 48309 USA

来源：

DISCRETE MATHEMATICS | 2011年 / 311卷 / 16期

基金：

中国国家自然科学基金;

关键词：

Edge-connectivity; Orbit; Super-edge-connected; Transitive graph; CAYLEY-GRAPHS;

D O I：

10.1016/j.disc.2011.04.016

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It is well known that the edge-connectivity of a simple, connected, vertex-transitive graph attains its regular degree. It is then natural to consider the relationship between the graph's edge-connectivity and the number of orbits of its automorphism group. In this paper, we discuss the edge connectedness of graphs with two orbits of the same size, and characterize when these double-orbit graphs are maximally edge connected and superedge-connected. We also obtain a sufficient condition for some double-orbit graphs to be lambda'-optimal. Furthermore, by applying our results we obtain some results on vertex/edge-transitive bipartite graphs, mixed Cayley graphs and half vertex-transitive graphs. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：1768 / 1777

页数：10

共 26 条

[11] Maximally edge-connected and vertex-connected graphs and digraphs: A survey [J].

Hellwig, Angelika ;

Volkmann, Lutz .

DISCRETE MATHEMATICS, 2008, 308 (15) :3265-3296

[12] SYMMETRY IN INTERCONNECTION NETWORKS BASED ON CAYLEY-GRAPHS OF PERMUTATION-GROUPS - A SURVEY [J].

LAKSHMIVARAHAN, S ;

JWO, JS ;

DHALL, SK .

PARALLEL COMPUTING, 1993, 19 (04) :361-407

[13]

Li QL, 1999, NETWORKS, V33, P157, DOI 10.1002/(SICI)1097-0037(199903)33:2<157::AID-NET6>3.0.CO

[14]

2-D

[15] Edge-connectivity of regular graphs with two orbits [J].

Liu, Fengxia ;

Meng, Jixiang .

DISCRETE MATHEMATICS, 2008, 308 (16) :3711-3716

[16]

Lovasz L., 1993, Combinatorial Problems and Exercises

[17]

LU Z, 2006, ARS COMBINATORIA, P177

[18] MINIMAL EDGE-N-CONNECTED GRAPHS [J].

MADER, W .

MATHEMATISCHE ANNALEN, 1971, 191 (01) :21-&

[19] Optimally super-edge-connected transitive graphs [J].

Meng, JX .

DISCRETE MATHEMATICS, 2003, 260 (1-3) :239-248

[20] λ′-optimally connected mixed Cayley graphs [J].

Tian, Yingzhi ;

Meng, Jixiang .

APPLIED MATHEMATICS LETTERS, 2011, 24 (06) :872-877

← 1 2 3 →