Contractible subgraphs in k‐connected graphs |
| |
Authors: | Zemin Jin Xingxing Yu Xiaoyan Zhang |
| |
Affiliation: | 1. Center for Combinatorics, LPMC, Nankai University, Tianjin 300071 P.R. China;2. School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332 |
| |
Abstract: | For a graph G we define a graph T(G) whose vertices are the triangles in G and two vertices of T(G) are adjacent if their corresponding triangles in G share an edge. Kawarabayashi showed that if G is a k‐connected graph and T(G) contains no edge, then G admits a k‐contractible clique of size at most 3, generalizing an earlier result of Thomassen. In this paper, we further generalize Kawarabayashi's result by showing that if G is k‐connected and the maximum degree of T(G) is at most 1, then G admits a k‐contractible clique of size at most 3 or there exist independent edges e and f of G such that e and f are contained in triangles sharing an edge and G/e/f is k‐connected. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 121–136, 2007 |
| |
Keywords: | graph connectivity contractible subgraph |
|
|