2011/01/20 by Shasha Li, Xueliang Li, Li, Shasha +3 · 1 citation
Computer Science · Mathematics · #05C05 #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #math.CO #msc:05C05 #msc:05C40
paper · pdf · doi:10.48550/arxiv.1101.3811
9 pages
openalex publication_date 2011/01/20 · arxiv created 2011/06/09 · arxiv updated 2015/03/17 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Let G be a nontrivial connected graph of order n and k an integer with 2≤ k≤ n. For a set S of k vertices of G, let κ(S) denote the maximum number ℓ of edge-disjoint trees T1,T2,...,T_ℓ in G such that V(Ti)∩ V(Tj)=S for every pair i,j of distinct integers with 1≤ i,j≤ ℓ. Chartrand et al. generalized the concept of connectivity as follows: The k-connectivity, denoted by κk(G), of G is defined by κk(G)=min\κ(S)\, where the minimum is taken over all k-subsets S of V(G). Thus κ2(G)=κ(G), where κ(G) is the connectivity of G. This paper mainly focuses on the minimal number of edges of a graph G with κ3(G)= 2. For a graph G of order v(G) and size e(G) with κ3(G)= 2, we obtain that e(G)≥ 6/5v(G), and the lower bound is sharp by showing a class of examples attaining the lower bound.