2011/06/22 by Shasha Li, Xueliang Li, Li, Shasha +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Interconnection Networks and Systems #math.CO #msc:05C05 #msc:05C40
paper · pdf · doi:10.48550/arxiv.1106.4411
7 pages
arxiv created 2011/06/22 · arxiv updated 2011/06/23
The concept of generalized k-connectivity κk(G) of a graph G was introduced by Chartrand et al. in recent years. In our early paper, extremal theory for this graph parameter was started. We determined the minimal number of edges of a graph of order n with κ3= 2, i.e., for a graph G of order n and size e(G) with κ3(G)= 2, we proved that e(G)≥ (6/5)n, and the lower bound is sharp by constructing a class of graphs, only for n≡ 0 (mod 5) and n≠ 10. In this paper, we improve the lower bound to \lceil(6/5)n\rceil. Moreover, we show that for all n≥ 4 but n= 9, 10, there always exists a graph of order n with κ3= 2 whose size attains the lower bound \lceil(6/5)n\rceil. Whereas for n= 9, 10 we give examples to show that \lceil(6/5)n\rceil+1 is the best possible lower bound. This gives a clear picture on the minimal size of a graph of order n with generalized connectivity κ3= 2.