On a closure concept in claw-free graphs.pdf

On a closure concept in claw-free graphsZdenek RyjacekDepartment of MathematicsUniversity of West BohemiaUniverzitn 22306 14 Plzen, Czech RepublicSeptember 25, 1996AbstractIf G is a claw-free graph, then there is a graph cl(G) such that(i) G is a spanning subgraph of cl(G),(ii) cl(G) is a line graph of a triangle-free graph, and(iii) the length of a longest cycle in G and in cl(G) is the same.A sucient condition for hamiltonicity in claw-free graphs, the equivalence of someconjectures on hamiltonicity in 2-tough graphs and the hamiltonicity of 7-connectedclaw-free graphs are obtained as corollaries.1 IntroductionIn this paper, a graph will be a nite undirected graph G = (V (G); E(G)) without loopsand multiple edges. For terminology and notation not dened here we refer to [1]. For anyset A  V (G) we denote by hAi the induced subgraph on A, GA stands for hV (G) nAiand !(GA) denotes the number of components of GA. The (vertex) connectivity ofG will be denoted by (G) and the circumference of G (i.e., the length of a longest cyclein G) will be denoted by c(G). The line graph of a graph G will be denoted by L(G). Bya clique we mean a (not necessarily maximal) complete subgraph of G.If H is a graph, then we say that a graph G is H-free if G contains no copy of H asan induced subgraph. Specically, the four-vertex star K1;3 will be also called the clawand in this case we say that G is claw-free. Whenever vertices of a claw are listed, itscenter (i.e., the only vertex of degree 3) will be always the rst vertex of the list. It iswell known (and can be easily checked) that every line graph is claw-free.1 For a vertex x 2 V (G), the set NG(x) = fy 2 V (G) : xy 2 E(G)g is called theneighborhood of x in G. We say that x is a locally connected vertex if hNG(x)i is aconnected graph. The set of all locally connected vertices of G will be denoted byMloc(G).If Mloc(G) = V (G), then we say that G is locally connected.Oberly and Sumner [7] proved that every connected, loc