Title of article
Almost All 3-Connected Graphs Contain a Contractible Set of k Vertices
Author/Authors
Kriesell، نويسنده , , Matthias، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2001
Pages
15
From page
305
To page
319
Abstract
McCuaig and Ota conjectured that every sufficiently large 3-connected graph G contains a connected subgraph H on k vertices such that G−V(H) is 2-connected. We prove the weaker statement that every sufficiently large 3-connected graph G contains a not necessarily connected subgraph H on k vertices such that G−V(H) is 2-connected.
Keywords
Longest induced path , connectivity , Reduction , longest cycle , contractable subgraph
Journal title
Journal of Combinatorial Theory Series B
Serial Year
2001
Journal title
Journal of Combinatorial Theory Series B
Record number
1526916
Link To Document