A solution to a conjecture on the generalized connectivity of graphs |
| |
| Authors: | Lily Chen Xueliang Li Mengmeng Liu Yaping Mao |
| |
| Institution: | 1.School of Mathematics Science,Huaqiao University,Quanzhou,People’s Republic of China;2.Center for Combinatorics and LPMC-TJKLC,Nankai University,Tianjin,People’s Republic of China;3.Department of Mathematics,Lanzhou Jiaotong University,Lanzhou,People’s Republic of China;4.Department of Mathematics,Qinghai Normal University,Xining,People’s Republic of China |
| |
| Abstract: | The generalized k-connectivity \(\kappa _k(G)\) of a graph G was introduced by Chartrand et al. in (Bull Bombay Math Colloq 2:1–6, 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 consider the computational complexity of the generalized connectivity and generalized edge-connectivity of a graph. We give a confirmative solution to a conjecture raised by S. Li in Ph.D. Thesis (2012). We also give a polynomial-time algorithm to a problem of generalized k-edge-connectivity. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
