Arc-disjoint Steiner Cycles in Digraphs

Abstract

Let $D=(V(D),A(D))$ be a digraph of order $n$ and let $S\subseteq V(D)$ with $2\le |S|\le n$. A directed cycle $C$ of $D$ is called a directed $S$-Steiner cycle (or, an $S$-cycle for short) if $S\subseteq V(C)$. Steiner cycles have applications in reliable designs for telecommunication and transportation networks. Two $S$-cycles are called arc-disjoint if they have no common arcs. We use $\hat{I}{»}_S^c(D)$ to denote the maximum number of pairwise arc-disjoint $S$-cycles in $D$. The directed cycle $k$-arc-connectivity of $D$ is defined as $$\hat{I}{»}_k^c(D)=\min \left\{\hat{I}{»}_S^c(D)\mid S\subseteq V(D),\left|S\right|=k,2\le k\le n\right\}.$$ In this paper, we determine the complexity for $\hat{I}{»}_S^c(D)$ on Eulerian digraphs, planar digraphs and symmetric digraphs. We also obtain exact values of $\hat{I}{»}_k^c(D)$ on complete digraphs, complete bipartite digraphs and complete regular multipartite digraphs.