Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs

preprint2016arXivOpen access

Abstract

A graph is called \emph{claw-free} if it contains no induced subgraph isomorphic to K1,3K_{1,3}. Matthews and Sumner proved that a 2-connected claw-free graph GG is hamiltonian if every vertex of it has degree at least (∣V(G)∣−2)/3(|V(G)|-2)/3. At the workshop C\&C (Novy Smokovec, 1993), Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of NN (the graph obtained from a triangle by adding three disjoint pendant edges). Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z1Z_1 (the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphs HH such that a 2-connected claw-free graph GG is hamiltonian if each end-vertex of every induced copy of HH in GG has degree at least ∣V(G)∣/3+1|V(G)|/3+1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.