The minimal size of a graph with given generalized 3-edge-connectivity

2012/01/18 by Xueliang Li, Li, Xueliang, Yaping Mao +1
Computer Science · Materials Science · Mathematics · #05C05 #05C40 #05C75 #Advanced Graph Theory Research #Carbon and Quantum Dots Applications #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #math.CO #msc:05C05 #msc:05C40 #msc:05C75

paper · pdf · doi:10.48550/arxiv.1201.3699

10 pages

openalex publication_date 2012/01/18 · arxiv created 2013/07/09 · arxiv updated 2013/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For S⊆ V(G) and |S|≥ 2, λ(S) is the maximum number of edge-disjoint trees connecting S in G. For an integer k with 2≤ k≤ n, the generalized k-edge-connectivity λ_k(G) of G is then defined as λ_k(G)= min\λ(S) : S⊆ V(G) and |S|=k\. It is also clear that when |S|=2, λ₂(G) is nothing new but the standard edge-connectivity λ(G) of G. In this paper, graphs of order n such that λ₃(G)=n-3 is characterized. Furthermore, we determine the minimal number of edges of a graph of order n with λ₃=1,n-3,n-2 and give a sharp lower bound for 2≤ λ₃≤ n-4.

Citations

• The generalized 3-connectivity of Cartesian product graphs

Related

• The minimal size of a graph with generalized connectivity κ₃ = 2
• Note on the minimal size of a graph with generalized connectivity kappa₃= 2
• The minimal size of graphs with given pendant-tree connectivity
• Extremality and Sharp Bounds for the k-edge-connectivity of Graphs
• Sharp bounds for the generalized connectivity κ₃(G)