2023/10/25 by Chenxu Yang, Ping Li, Yang, Chenxu +7
Computer Science · Engineering · Materials Science · #Advanced Optical Network Technologies #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graphene research and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2310.16463
openalex publication_date 2023/10/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph and S⊆ V(G) with |S|≥ 2. Then the trees T1, T2, ⋯, T_ℓ in G are internally disjoint Steiner trees connecting S (or S-Steiner trees) if E(Ti) ∩ E(Tj )=∅ and V(Ti)∩ V(Tj)=S for every pair of distinct integers i,j, 1 ≤ i, j ≤ ℓ. Similarly, if we only have the condition E(Ti) ∩ E(Tj )=∅ but without the condition V(Ti)∩ V(Tj)=S, then they are edge-disjoint Steiner trees. The generalized k-connectivity, denoted by κk(G), of a graph G, is defined as κk(G)=min\κG(S)|S ⊆ V(G) \textrmand |S|=k \, where κG(S) is the maximum number of internally disjoint S-Steiner trees. The generalized local edge-connectivity λG(S) is the maximum number of edge-disjoint Steiner trees connecting S in G. The \it generalized k-edge-connectivity λk(G) of G is defined as λk(G)=min\λG(S) | S⊆ V(G) and |S|=k\. These measures are generalizations of the concepts of connectivity and edge-connectivity, and they and can be used as measures of vulnerability of networks. It is, in general, difficult to compute these generalized connectivities. However, there are precise results for some special classes of graphs. In this paper, we obtain the exact value of λk(S(n,ℓ)) for 3≤ k≤ ℓn, and the exact value of κk(S(n,ℓ)) for 3≤ k≤ ℓ, where S(n, ℓ) is the Sierpiński graphs with order ℓn. As a direct consequence, these graphs provide additional interesting examples when λk(S(n,ℓ))=κk(S(n,ℓ)). We also study the some network properties of Sierpiński graphs.