Article ID Journal Published Year Pages File Type
4648766 Discrete Mathematics 2008 6 Pages PDF
Abstract

Let G=(V,E)G=(V,E) be a simple connected graph and x∈V(G)x∈V(G). The set {xg:g∈Aut(G)}{xg:g∈Aut(G)} is called an orbit of Aut(G)Aut(G). In this paper, we determine the edge connectivity of 3-regular and 4-regular connected graphs with two orbits, and prove the existence of k-regular m-edge-connected graphs with two orbits for some given integers k and m. Furthermore, we prove that the edge connectivity of a k  -regular connected graph with two orbits and girth⩾5girth⩾5 attains its regular degree k.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,