2013/01/20 by Xueliang Li, Yan Zhao, Li, Xueliang +1
Mathematics · #05C05 #05C40 #05C75 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C05 #msc:05C40 #msc:05C75
paper · pdf · doi:10.48550/arxiv.1301.4623
11 pages
arxiv created 2013/01/20 · arxiv updated 2013/01/22
The problem of determining the largest number f(n;κ≤ ℓ) of edges for graphs with n vertices and maximal local connectivity at most ℓ was considered by Bollobás. Li et al. studied the largest number f(n;κ3≤2) of edges for graphs with n vertices and at most two internally disjoint Steiner trees connecting any three vertices. In this paper, we further study the largest number f(n;κk=1) of edges for graphs with n vertices and exactly one Steiner tree connecting any k vertices with k≥ 3. It turns out that this is not an easy task to finish, not like the same problem for the classical connectivity parameter. We determine the exact values of f(n;κk=1) for k=3,4,n, respectively, and characterize the graphs which attain each of these values.