Contractible edges in some k-connected graphs |
| |
Authors: | Yingqiu Yang Liang Sun |
| |
Institution: | 1. School of Mathematics, Beijing Institute of Technology, Beijing, 100081, P.R. China
|
| |
Abstract: | An edge e of a k-connected graph G is said to be k-contractible (or simply contractible) if the graph obtained from G by contracting e (i.e., deleting e and identifying its ends, finally, replacing each of the resulting pairs of double edges by a single edge) is still k-connected. In 2002, Kawarabayashi proved that for any odd integer k ? 5, if G is a k-connected graph and G contains no subgraph D = K 1 + (K 2 ∪ K 1,2), then G has a k-contractible edge. In this paper, by generalizing this result, we prove that for any integer t ? 3 and any odd integer k ? 2t + 1, if a k-connected graph G contains neither K 1 + (K 2 ∪ K 1,t ), nor K 1 + (2K 2 ∪ K 1,2), then G has a k-contractible edge. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|