Hamiltonicity in claw-free graphs through induced bulls
type: Item
instance of: scholarly article
title: Hamiltonicity in claw-free graphs through induced bulls
zbMATH Open document ID: 0823.05040
DOI: 10.1016/0012-365X(94)00292-Q
author: Zdeněk Ryjáček
published in: Discrete Mathematics
publication date: 1995-07-03T00:00:00Z
review text: A claw is the complete bipartite graph \(K_{1, 3}\) and a bull is the unique graph with the degree sequence 3, 3, 2, 1, 1. A graph \(G\) is claw- free if \(G\) contains no induced subgraph isomorphic to the claw. In this paper, the following conjecture proposed by \textit{H. Broersma} and \textit{H. J. Veldman} [Contemporary methods in graph theory. In honour of Prof. Dr. K. Wagner, 181-194 (1990; Zbl 0723.05082)] is proved: Let \(G\) be a 2- connected claw-free graph. Suppose that, for each induced bull \(B\) in \(G\), the degree one vertices of \(B\) have some common neighbor in \(G\). Then \(G\) contains a Hamilton cycle.
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 769311
zbMATH Keywords: claw
zbMATH Keywords: bull
zbMATH Keywords: induced subgraph
zbMATH Keywords: claw-free graph
zbMATH Keywords: Hamilton cycle
MaRDI profile type: Publication
cites work: Q3211339
cites work: Updating the hamiltonian problem—A survey
description: scientific article; zbMATH DE number 769311