On the edge-connectivity of graphs with two orbits of the same size |
| |
Authors: | Weihua Yang Zhao Zhang Xiaofeng Guo Eddie Cheng László Lipták |
| |
Institution: | aSchool of Mathematical Science, Xiamen University, Xiamen Fujian 361005, China;bDepartment of Mathematics, Xinjiang University, Urumqi 830046, China;cDepartment of Mathematics and Statistics, Oakland University, Rochester, MI 48309, USA |
| |
Abstract: | 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. |
| |
Keywords: | Edge-connectivity Orbit Super-edge-connected Transitive graph |
本文献已被 ScienceDirect 等数据库收录! |
|