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

详细信息    查看全文

• 作者：Weihua Yang^a ; ^{ywh222@163.com"" rel=""nofollow} ; Zhao Zhang^b ; Xiaofeng Guo^a ; Eddie Cheng^c ; L&#xe1 ; szló ; Lipt&#xe1 ; k^c
• 关键词：Edge-connectivity ; Orbit ; Super-edge-connected ; Transitive graph
• 刊名：Discrete Mathematics
• 出版年：2011
• 出版时间：28 August 2011
• 年：2011
• 卷：311
• 期：16
• 页码：1768-1777
• 全文大小：273 K

文摘

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 super-edge-connected. We also obtain a sufficient condition for some double-orbit graphs to be λ^′-optimal. Furthermore, by applying our results we obtain some results on vertex/edge-transitive bipartite graphs, mixed Cayley graphs and half vertex-transitive graphs.