We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
STRONG SUBGRAPH 2-ARC-CONNECTIVITY AND ARC-STRONG CONNECTIVITY OF CARTESIAN PRODUCT OF DIGRAPHS.
- Authors
YILING DONG; GUTIN, GREGORY; YUEFANG SUN
- Abstract
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 arcdisjoint if A(D1) ∩ A(D2) = ∅. Let λS(D) be the maximum number of pairwise arc-disjoint S-strong subgraphs in D. The strong subgraph k-arcconnectivity 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 edgeconnectivity 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: λ(Gk) = k · min {δ+ (G), δ- (G)}. Then we study the strong nnectivity 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) > λ2(H). We also obtain exact values for λ2(G✷H), where G and H are digraphs from some digraph families.
- Subjects
UNDIRECTED graphs; SUBGRAPHS; GENERALIZATION; FAMILIES; TREES
- Publication
Discussiones Mathematicae: Graph Theory, 2024, Vol 44, Issue 3, p913
- ISSN
1234-3099
- Publication type
Article
- DOI
10.7151/dmgt.2479