Article in volume
Authors:
Title:
Strong subgraph 2-arc-connectivity and arc-strong connectivity of Cartesian product of digraphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(3) (2024) 913-931
Received: 2022-03-31 , Revised: 2022-10-27 , Accepted: 2022-10-27 , Available online: 2022-12-08 , https://doi.org/10.7151/dmgt.2479
Abstract:
Let $D=(V,A)$ be a digraph of order $n$, $S$ a subset of $V$ of size $k$ and
$2\le k\leq 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)=\emptyset$.
Let $\lambda_S(D)$ be the maximum number of pairwise arc-disjoint $S$-strong
subgraphs in $D$. The strong subgraph $k$-arc-connectivity is defined as
$$
\lambda_k(D)=\min\{\lambda_S(D)| 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\Box 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). Using this formula, we get a new formula for the
arc-connectivity of Cartesion product of $k\ge 2$ copies of a strong digraph $G$:
$\lambda(G^{k})=k\cdot \min\left \{ \delta ^{+}\left ( G \right ),\delta ^{-}
\left ( G \right )\right \}$.
Then we study the strong subgraph 2-arc-connectivity of Cartesian product
$\lambda_2(G\Box H)$ and prove that $ \min\left \{ \lambda (G)
|H|, \lambda (H)|G|, %\\
\delta ^{+ }(G)+ \delta ^{+ } (H), \right.$ \linebreak
$\left.\delta ^{-} (G)+ \delta ^{- } (H) \right \}\ge\lambda_2(G\Box H)\ge
\lambda_2(G)+\lambda_2(H)-1.$ The upper bound for
$\lambda_2(G\Box H)$ is sharp and is a simple corollary of the formula for
$\lambda(G\Box H)$. The lower bound for $\lambda_2(G\Box H)$ is either sharp
or almost sharp i.e., differs by 1 from the sharp bound. We improve the lower
bound under an additional condition and prove its sharpness by showing that
$\lambda_2(G\Box H)\geq \lambda_2(G)+ \lambda_2(H),$ where $G$ and $H$ are two
strong digraphs such that $\delta ^{+}\left (H \right)> \lambda _{2}(H)$.
We also obtain exact values for $\lambda_2(G\Box H)$, where $G$ and $H$ are
digraphs from some digraph families.
Keywords:
connectivity, strong subgraph arc-connectivity, Cartesian product, tree connectivity
References:
- J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd Edition (Springer, London, 2009).
https://doi.org/10.1007/978-1-84800-998-1 - J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, Berlin, 2008).
- M. Hager, Pendant tree-connectivity, J. Combin. Theory Ser. B 38 (1985) 179–189.
https://doi.org/10.1016/0095-8956(85)90083-8 - R.H. Hammack, Digraphs products, in: Classes of Directed Graphs, J. Bang-Jensen and G. Gutin (Ed(s)), (Springer 2018) 467–515.
https://doi.org/10.1007/978-3-319-71840-8_10 - W. Imrich, S. Klavžar and D.F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Product (A K Peters, Ltd., Wellesley, MA, 2008).
https://doi.org/10.1201/b10613 - S. Klavžar and S. Špacapan, On the edge-connectivity of Cartesian product graphs, Asian-Eur. J. Math. 1 (2008) 93–98.
https://doi.org/10.1142/S1793557108000102 - X. Li and Y. Mao, Generalized Connectivity of Graphs (Springer, Switzerland, 2016).
https://doi.org/10.1007/978-3-319-33828-6 - X. Li, Y. Mao and Y. Sun, On the generalized $($edge$-)$connectivity of graphs, Australas. J. Combin. 58 (2014) 304–319.
- S. Špacapan, Connectivity of Cartesian products of graphs, Appl. Math. Lett. 21 (2008) 682–685.
https://doi.org/10.1016/j.aml.2007.06.010 - Y. Sun and G. Gutin, Strong subgraph connectivity of digraphs: a survey, J. Interconnection Networks 21(2) (2021) 2142004.
https://doi.org/10.1142/S0219265921420044 - Y. Sun and G. Gutin, Strong subgraph connectivity of digraphs, Graphs Combin. 37 (2021) 951–970.
- Y. Sun, G. Gutin, A. Yeo and X. Zhang, Strong subgraph k-connectivity, J. Graph Theory 92 (2019) 5–18.
https://doi.org/10.1002/jgt.22437 - Y. Sun, G. Gutin and X. Zhang, Packing strong subgraph in digraphs, Discrete Optim. 46 (2022) 100745.
- J.-M. Xu and C. Yang, Connectivity of Cartesian product graphs, Discrete Math. 306 (2006) 159–165.
https://doi.org/10.1016/j.disc.2005.11.010
Close