2012/12/30 by Xueliang Li, Li, Xueliang, Yaping Mao +1
Computer Science · Materials Science · Mathematics · #Advanced Graph Theory Research #Graphene research and applications #Interconnection Networks and Systems #math.CO #msc:05C05 #msc:05C40 #msc:05C76
paper · pdf · doi:10.48550/arxiv.1212.6692
16 pages
arxiv created 2012/12/30 · arxiv updated 2013/01/01
Let G be a graph, S be a set of vertices of G, and λ(S) be the maximum number ℓ of pairwise edge-disjoint trees T1, T2,..., Tℓ in G such that S⊆ V(Ti) for every 1≤ i≤ ℓ. The generalized k-edge-connectivity λk(G) of G is defined as λk(G)= min\λ(S) | S⊆ V(G) and |S|=k\. Thus λ2(G)=λ(G). In this paper, we consider the Nordhaus-Gaddum-type results for the parameter λk(G). We determine sharp upper and lower bounds of λk(G)+λk(G) and λk(G)... λk(G) for a graph G of order n, as well as for a graph of order n and size m. Some graph classes attaining these bounds are also given.