On Cyclic Edge Connectivity of Regular Graphs with Two Orbits

Abstract

A cyclic edge-cut of a graph $G$ is an edge set whose removal separates two cycles. If $G$ has a cyclic edge-cut, it is said to be cyclically separable. For a cyclically separable graph $G$, the cyclic edge-connectivity $c\lambda (G)$ is the cardinality of a minimum cyclic edge-cut of $G$. Let $\zeta (G)=min\{w(X)\mid X\text{ induces a shortest cycle in }G\}$, where $w(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\lambda (G)=\zeta (G)$ is said to be cyclically optimal. In this work, we discuss the cyclic edge connectivity of regular double-orbit graphs. Furthermore, as a corollary, we obtain a sufficient condition for mixed Cayley graphs, introduced by Chen and Meng $[3]$, to be cyclically optimal.