Longest cycles in regular 2-connected claw-free graphs

✍ Scribed by MingChu Li

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 884 KB
• Volume: 137
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)e0142-q

✦ Synopsis

In this paper, we show that every 2-connected, k-regular claw-free graph on n vertices contains a cycle of length at least min {4k-2, n} (k >~ 8), and this result is best possible.

I. Introduction

All graphs considered here are undirected and finite, without loops or multiple edges. A graph G is called claw-free if it does not contain a K1, 3 as an induced subgraph. Let 6(G) and k(G) denote the minimum degree and the connectivity of a graph G, respectively. For a subgraph H of G, a subset S of V(G) and x6 V(G), let G -H and G IS] denote the subgraphs of G induced by V(G)-V(H) and S, respectively, Nn(x)= N(x)n V(H), N(S)= Ux~sN(x), NH(S)= N(S)~ V(H), an(x)= I Nn(x)l, and E~(A,B)={uv~E(G): u~A, v6B} and eo(A,B)=IEG(A,B)r for A,B in V(G). Let P=xlxz...xl be a path in G, then uPv denotes the path UXlX2...xiv or uxix¢\_l...XlV.
Let C be a cycle on which we define an orientation, and its vertices are denoted by cl, c2, ..., c,, in order around C (where m = I V(C) I). Set cl + = ci + 1 and cf = ci-1, and let c~Ccj=cic~+l...c s and Cs ('C~=Cfj\_l...c~(i 8), and this result is best possible.