2013/04/23 by Lily Chen, Chen, Lily, Xueliang Li +5
Mathematics · #05C05 #05C40 #68Q25 #68R10 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C05 #msc:05C40 #msc:68Q25 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1304.6153
12 pages. arXiv admin note: text overlap with arXiv:1207.1838
arxiv created 2013/04/23 · arxiv updated 2013/04/24
The generalized k-connectivity κk(G) of a graph G was introduced by Chartrand et al. in 1984, which is a nice generalization of the classical connectivity. Recently, as a natural counterpart, Li et al. proposed the concept of generalized edge-connectivity for a graph. In this paper, we determine the computational complexity of the generalized connectivity and generalized edge-connectivity of a graph. Two conjectures are also proved to be true.