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

DOI10.1007/S10114-016-4686-1MaRDI QIDQ327292zbMATH OpenOpenAlexFDO

Authors Roman Čada, Binlong Li, Shenggui Zhang, Bo Ning

Publication date 19 October 2016

Published in Acta Mathematica Sinica, English Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.4585

zbMATH Keywords

claw-free graphend-vertexHamiltonian graphinduced subgraphlarge degree

Mathematics Subject Classification ID

Vertex degrees (05C07) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Abstract: A graph is called emph{claw-free} if it contains no induced subgraph isomorphic to $K_{1,3}$. Matthews and Sumner proved that a 2-connected claw-free graph $G$ is hamiltonian if every vertex of it has degree at least $(|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 $N$ (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 $Z_1$ (the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphs $H$ such that a 2-connected claw-free graph $G$ is hamiltonian if each end-vertex of every induced copy of $H$ in $G$ has degree at least $|V(G)|/3+1$. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.

Recommendations

• Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs
• Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs. II
• Hamiltonian claw-free graphs and \(o\)-heavy graphs involving induced cycles
• Induced nets and Hamiltonicity of claw-free graphs
• Degree conditions restricted to induced paths for Hamiltonicity of claw-heavy graphs
• Hamiltonicity and degrees of adjacent vertices in claw-free graphs
• The Hamilton-connectivity with the degree sum of non-adjacent subgraphs of claw-free graphs
• Hamiltonicity in claw-free graphs through induced bulls
• Degree and neighborhood conditions for Hamiltonicity of claw-free graphs
• Hamiltonicity in claw-free graphs

Cites work

• Degree conditions on claws and modified claws for Hamiltonicity of graphs
• Forbidden subgraphs, hamiltonicity and closure in claw-free graphs
• Graph theory with applications
• Longest paths and cycles in K1,3-free graphs
• Minimal 2-connected non-Hamiltonian claw-free graphs
• On a closure concept in claw-free graphs
• Reflections on graph theory
• Some Theorems on Abstract Graphs

Cited in

(7)

• Induced nets and Hamiltonicity of claw-free graphs
• Hamiltonian line graphs with local degree conditions
• Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs. II
• Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs
• scientific article; zbMATH DE number 4183448 (Why is no real title available?)
• Local degree conditions for Hamiltonicity of claw-free graphs
• Hamiltonian claw-free graphs with path-type local degree conditions

This page was built for publication: Induced subgraphs with large degrees at end-vertices for Hamiltonicity of claw-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q327292)