Strong subgraph 2-arc-connectivity and arc-strong connectivity of Cartesian product of digraphs

Abstract

Let $D=(V,A)$ be a digraph of order $n$, $S$ a subset of $V$ of size $k$ and $2\le k\le n$. A strong subgraph $H$ of $D$ is called an $S$-strong subgraph if $S\subseteq V(H)$. A pair of $S$-strong subgraphs $D_1$ and $D_2$ are said to be arc-disjoint if $A(D_1)\cap A(D_2)=\varnothing$. Let ${\lambda }_S(D)$ be the maximum number of arc-disjoint $S$-strong subgraphs in $D$. The strong subgraph $k$-arc-connectivity is defined as $${\lambda }_k(D)=\min \{{\lambda }_S(D)\mid S\subseteq V(D),|S|=k\}.$$ The parameter ${\lambda }_k(D)$ can be seen as a generalization of classical edge-connectivity of undirected graphs. In this paper, we first obtain a formula for the arc-connectivity of Cartesian product $\lambda (G\square H)$ of two digraphs $G$ and $H$ generalizing a formula for edge-connectivity of Cartesian product of two undirected graphs obtained by Xu and Yang (2006). Then we study the strong subgraph 2-arc-connectivity of Cartesian product ${\lambda }_2(G\square H)$ and prove that $\min \left\{\lambda \left(G\right)\left|H\right|,\lambda \left(H\right)\left|G\right|,{\delta }^{+}\left(G\right)+{\delta }^{+}\left(H\right),{\delta }^{-}\left(G\right)+{\delta }^{-}\left(H\right)\right\}\ge {\lambda }_2(G\square H)\ge {\lambda }_2(G)+{\lambda }_2(H)-1.$ The upper bound for ${\lambda }_2(G\square H)$ is sharp and is a simple corollary of the formula for $\lambda (G\square H)$. The lower bound for ${\lambda }_2(G\square H)$ is either sharp or almost sharp i.e. differs by 1 from the sharp bound. We also obtain exact values for ${\lambda }_2(G\square H)$, where $G$ and $H$ are digraphs from some digraph families.

arXiv admin note: text overlap with arXiv:1805.01687