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\leq |S|\leq 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 $\lambda_{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 $$\lambda_{k}^{c} (D)=\min\left \{ \lambda _{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 $\lambda_{S}^{c} (D)$ on Eulerian digraphs, planar digraphs and symmetric digraphs. We also obtain exact values of $\lambda_{k}^{c} (D)$ on complete digraphs, complete bipartite digraphs and complete regular multipartite digraphs.