Premium
Contractible subgraphs in k ‐connected graphs
Author(s) -
Jin Zemin,
Yu Xingxing,
Zhang Xiaoyan
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20227
Subject(s) - combinatorics , mathematics , contractible space , graph , connectivity , vertex connectivity , clique , discrete mathematics , vertex (graph theory)
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