Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419307 | Discrete Applied Mathematics | 2015 | 11 Pages |
Abstract
For a graph GG and a set SS of vertices of GG, let λ(S)λ(S) denote the maximum number ℓℓ of pairwise edge-disjoint Steiner trees T1,T2,⋯,TℓT1,T2,⋯,Tℓ in GG such that S⊆V(Ti)S⊆V(Ti) for every 1≤i≤ℓ1≤i≤ℓ. For an integer kk with 2≤k≤n2≤k≤n, where nn is the order of GG, the generalized kk-edge-connectivity λk(G)λk(G) of GG is defined as λk(G)=min{λ(S)∣S⊆V(G)and|S|=k}. In this paper, we consider the Nordhaus–Gaddum-type results for the parameter λk(G)λk(G). We obtain sharp upper and lower bounds of λk(G)+λk(G¯) and λk(G)⋅λk(G¯) for a graph GG of order nn, as well as a graph GG of order nn and size mm. Some graph classes attaining these bounds are also given.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Xueliang Li, Yaping Mao,