Contractible Cycles in Graphs with Girth at Least 5

✍ Scribed by Yoshimi Egawa

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 569 KB
• Volume: 74
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1998.1844

✦ Synopsis

Let k 3 be an integer. We show that if G is a k-connected graph with girth at least 5, then G has an induced cycle Q such that G&V(Q) is (k&1)-connected.

1998 Academic Press

1. Introduction

By a graph, we mean a finite, undirected, simple graph with no loops and no multiple edges.

Let G=(V(G ), E(G )) be a graph. For a subset X of V(G ), we let (X) =(X) G denote the graph induced by X in G, and let G&X denote the graph obtained from G by deleting X ; thus G&X=(V(G)&X). By a cycle of G, we mean a connected 2-regular nonempty subgraph of G. In this paper, cycles are denoted by letters such as

The following two theorems were proved by Y. Egawa [2], C. Thomassen [6], and C. Thomassen and B. Toft [7]: Theorem A [6]. Let k 4 be an integer, and let G be a k-connected graph. Then G has an induced cycle Q such that G&V(Q) is (k&3)-connected.

Theorem B [2; 7, Corollaries 1, 3]. Let k 3 be an integer, and let G be a k-connected graph with girth at least 4. Then G has an induced cycle Q such that G&V(Q ) is (k&2)-connected.