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

Dong, Yiling ; Gutin, Gregory ; Sun, Yuefang 

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 913-931

Résumé

Let D=(V,A) be a digraph of order n, S a subset of V of size k and 2≤ k≤ n. A strong subgraph H of D is called an S-strong subgraph if S⊆ V(H). A pair of S-strong subgraphs D_1 and D_2 are said to be arc-disjoint if A(D_1)∩ A(D_2)=∅. Let λ_S(D) be the maximum number of pairwise arc-disjoint S-strong subgraphs in D. The strong subgraph k-arc-connectivity is defined as λ_k(D)=min{λ_S(D)| S⊆ V(D), |S|=k}.The parameter λ_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 λ(G□ 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≥ 2 copies of a strong digraph G: λ(G^k)=k·min{δ ^+ (G),δ ^- (G) }. Then we study the strong subgraph 2-arc-connectivity of Cartesian product λ_2(G□ H) and prove that min{λ (G) |H|, λ (H)|G|, δ ^+ (G)+ δ ^+ (H), δ ^- (G)+ δ ^- (H) }≥λ_2(G□ H)≥λ_2(G)+λ_2(H)-1. The upper bound for λ_2(G□ H) is sharp and is a simple corollary of the formula for λ(G□ H). The lower bound for λ_2(G□ 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 λ_2(G□ H)≥λ_2(G)+ λ_2(H), where G and H are two strong digraphs such that δ ^+ (H ) gt; λ _2(H). We also obtain exact values for λ_2(G□ H), where G and H are digraphs from some digraph families.

Détail

Keywords: connectivity, strong subgraph arc-connectivity, Cartesian product, tree connectivity

Bibliographie

[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