DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

Y. Dong

Yiling Dong

Ningbo University

email: dongyilingnpc@163.com

G. Gutin

Gregory Gutin

email: gutin@cs.rhul.ac.uk

Y. Sun

Yuefang Sun

Ningbo University

email: yuefangsun2013@163.com

Title:

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

PDF

Source:

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:

  1. 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
  2. J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, Berlin, 2008).
  3. M. Hager, Pendant tree-connectivity, J. Combin. Theory Ser. B 38 (1985) 179–189.
    https://doi.org/10.1016/0095-8956(85)90083-8
  4. 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
  5. 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
  6. 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
  7. X. Li and Y. Mao, Generalized Connectivity of Graphs (Springer, Switzerland, 2016).
    https://doi.org/10.1007/978-3-319-33828-6
  8. X. Li, Y. Mao and Y. Sun, On the generalized $($edge$-)$connectivity of graphs, Australas. J. Combin. 58 (2014) 304–319.
  9. 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
  10. 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
  11. Y. Sun and G. Gutin, Strong subgraph connectivity of digraphs, Graphs Combin. 37 (2021) 951–970.
  12. 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
  13. Y. Sun, G. Gutin and X. Zhang, Packing strong subgraph in digraphs, Discrete Optim. 46 (2022) 100745.
  14. 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