On a Hamiltonian cycle in which specified vertices are not isolated
type: Item
instance of: scholarly article
title: On a Hamiltonian cycle in which specified vertices are not isolated
zbMATH Open document ID: 1015.05040
DOI: 10.1016/S0012-365X(02)00263-7
author: Atsushi Kaneko
author: Ken-ichi Kawarabayashi
author: Katsuhiro Ota
author: Kiyoshi Yoshimoto
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: Let \(G\) be a graph of order \(n\) and \(B\) a set of at least \(3n/4\) vertices. It is shown that if \(\delta(G) \geq n/2\), then \(G\) contains a Hamiltonian cycle such that each vertex of \(B\) is adjacent on the Hamiltonian cycle to some other vertex of \(B\). The condition \(\delta(G) \geq n/2\) is needed for the existence of a Hamiltonian cycle and \(|B|\geq 3n/4\) is needed to avoid an isolated vertex of \(B\) on the Hamiltonian cycle.
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1839023
zbMATH Keywords: Hamiltonian
zbMATH Keywords: specified vertices
reviewed by: Ralph Faudree
MaRDI profile type: Publication
full work available at URL: s0012-365x(02)00263-7
OpenAlex ID: W1966620549
description: scientific article; zbMATH DE number 1839023