2022/01/22 by Yiling Dong, Gregory Gutin, Dong, Yiling +3
Computer Science · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2201.09093
openalex publication_date 2022/01/22 · openalex created_date 2022/04/27 · openalex updated_date 2026/07/28
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 D1 and D2 are said to be arc-disjoint if A(D1)∩ A(D2)=∅. Let λS(D) be the maximum number of 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\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). Then we study the strong subgraph 2-arc-connectivity of Cartesian product λ2(G\Box H) and prove that min \ λ ( G ) | H | , λ ( H ) |G |,δ+ ( G )+ δ+ ( H ),δ- ( G )+ δ- ( H ) \≥λ2(G\Box H)≥ λ2(G)+λ2(H)-1. The upper bound for λ2(G\Box H) is sharp and is a simple corollary of the formula for λ(G\Box H). The lower bound for λ2(G\Box H) is either sharp or almost sharp i.e. differs by 1 from the sharp bound. We also obtain exact values for λ2(G\Box H), where G and H are digraphs from some digraph families.