Arc-Connectivity of Regular Digraphs with Two Orbits

Abstract

A strongly connected digraph \(D\) is said to be maximally arc connected if its arc-connectivity \(\lambda(D)\) attains its minimum degree \(\delta(D)\). For any vertex \(x\) of \(D\), the set \(\{x^g \mid g \in \text{Aut}(D)\}\) is called an orbit of \(\text{Aut}(D)\). Liu and Meng [ Fengxia Liu, Jixiang Meng, Edge-Connectivity of regular graphs with two orbits, Discrete Math. \(308 (2008) 3711-3717 \)] proved that the edge-connectivity of a \(k\)-regular connected graph with two orbits and girth \(\geq 5\) attains its regular degree \(k\). In the present paper, we prove the existence of \(k\)-regular \(m\)-arc-connected digraphs with two orbits for some given integer \(k\) and \(m\). Furthermore, we prove that the \(k\)-regular connected digraphs with two orbits, satisfying girth \( \geq k\) are maximally arc connected. Finally, we give an example to show that the girth bound \(k\) is best possible.