On cyclic edge-connectivity of transitive graphs |
| |
Authors: | Bing Wang |
| |
Institution: | College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang, 830046, China |
| |
Abstract: | A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is said to be cyclically separable. For a cyclically separable graph G, the cyclic edge-connectivity cλ(G) is the cardinality of a minimum cyclic edge-cut of G. In this paper, we first prove that for any cyclically separable graph G, , where ω(X) is the number of edges with one end in X and the other end in V(G)?X. A cyclically separable graph G with cλ(G)=ζ(G) is said to be cyclically optimal. The main results in this paper are: any connected k-regular vertex-transitive graph with k≥4 and girth at least 5 is cyclically optimal; any connected edge-transitive graph with minimum degree at least 4 and order at least 6 is cyclically optimal. |
| |
Keywords: | Cyclic edge-cut Cyclic edge-connectivity Cyclically optimal Vertex-transitive Edge-transitive |
本文献已被 ScienceDirect 等数据库收录! |
|