Connectivity keeping paths in k‐connected graphs |
| |
Authors: | W. Mader |
| |
Affiliation: | Department of Mathematics, Welfengarten 1, 30167 University Hannover, Germany |
| |
Abstract: | A result of G. Chartrand, A. Kaugars, and D. R. Lick [Proc Amer Math Soc 32 (1972), 63–68] says that every finite, k‐connected graph G of minimum degree at least ?3k/2? contains a vertex x such that G?x is still k‐connected. We generalize this result by proving that every finite, k‐connected graph G of minimum degree at least ?3k/2?+m?1 for a positive integer m contains a path P of length m?1 such that G?V(P) is still k‐connected. This has been conjectured in a weaker form by S. Fujita and K. Kawarabayashi [J Combin Theory Ser B 98 (2008), 805–811]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 61–69, 2010. |
| |
Keywords: | k‐connected graph paths |
|
|