The λ3-connectivity and κ3-connectivity of recursive circulants

摘要

Let S be a set of at least two vertices in a graph G. A subtree T of G is a S-Steiner tree if S ⊆ V (T). Two S-Steiner trees T1 and T2 are edge-disjoint (resp. internally disjoint) if E(T1)∩E(T2)=∅ (resp. E(T1)∩E(T2)=∅ and V(T1)∩V(T2)=S). Let λG(S) (resp. κG(S)) be the maximum number of edge-disjoint (resp. internally disjoint) S-Steiner trees in G, and let λk(G) (κk(G)) be the minimum λG(S) (resp. κG(S)) for S ranges over all k-subsets of V(G). Clearly, λ2(G) (resp. κ2(G)) is the classical edge-connectivity λ(G) (resp. connectivity κ(G)). In this paper, we study the λ3-connectivity and κ3-connectivity of a recursive circulant G, determine λ3(G)=δ(G)−1 for each recursive circulant G, and κ3(G)=δ(G)−1 for each recursive circulant G except G≅G(2m, 2).