2013/04/13 by Xueliang Li, Li, Xueliang, Yaping Mao +1
Computer Science · Mathematics · #05C05 #05C35 #05C40 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #math.CO #msc:05C05 #msc:05C35 #msc:05C40 #msc:05C75
paper · pdf · doi:10.48550/arxiv.1304.3774
19 pages
arxiv created 2013/04/13 · openalex publication_date 2013/04/13 · arxiv updated 2013/04/16 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
The concept of maximum local connectivity κ of a graph was introduced by Bollobás. One of the problems about it is to determine the largest number of edges f(n;κ≤ ℓ) for graphs of order n that have local connectivity at most ℓ. We consider a generalization of the above concept and problem. For S⊆ V(G) and |S|≥ 2, the generalized local connectivity κ(S) is the maximum number of internally disjoint trees connecting S in G. The parameter κk(G)=max\κ(S)|S⊆ V(G),|S|=k\ is called the maximum generalized local connectivity of G. This paper it to consider the problem of determining the largest number f(n;κk≤ ℓ) of edges for graphs of order n that have maximum generalized local connectivity at most ℓ. The exact value of f(n;κk≤ ℓ) for k=n,n-1 is determined. For a general k, we construct a graph to obtain a sharp lower bound.