On a hamiltonian cycle in which specified vertices are not isolated

Atsushi Kaneko; Ken Ichi Kawarabayashi; Katsuhiro Ota; Kiyoshi Yoshimoto

doi:10.1016/S0012-365X(02)00263-7

On a hamiltonian cycle in which specified vertices are not isolated

Atsushi Kaneko, Ken Ichi Kawarabayashi, Katsuhiro Ota, Kiyoshi Yoshimoto

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

Let G be a graph with n vertices and minimum degree at least n/2, and B a set of vertices with at least 3n/4 vertices. In this paper, we show that there exists a hamiltonian cycle in which every vertex in B is adjacent to some vertex in B.

Original language	English
Pages (from-to)	X85-91
Journal	Discrete Mathematics
Volume	258
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(02)00263-7
Publication status	Published - 2002 Dec 6

Keywords

A minimum degree
Dirac-type condition
Hamiltonian cycles
Specifed vertices

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0012-365X(02)00263-7

Cite this

@article{705d38c89a284b899d7db6f5f4a7fdd6,

title = "On a hamiltonian cycle in which specified vertices are not isolated",

abstract = "Let G be a graph with n vertices and minimum degree at least n/2, and B a set of vertices with at least 3n/4 vertices. In this paper, we show that there exists a hamiltonian cycle in which every vertex in B is adjacent to some vertex in B.",

keywords = "A minimum degree, Dirac-type condition, Hamiltonian cycles, Specifed vertices",

author = "Atsushi Kaneko and Kawarabayashi, {Ken Ichi} and Katsuhiro Ota and Kiyoshi Yoshimoto",

year = "2002",

month = dec,

day = "6",

doi = "10.1016/S0012-365X(02)00263-7",

language = "English",

volume = "258",

pages = "X85--91",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - On a hamiltonian cycle in which specified vertices are not isolated

AU - Kaneko, Atsushi

AU - Kawarabayashi, Ken Ichi

AU - Ota, Katsuhiro

AU - Yoshimoto, Kiyoshi

PY - 2002/12/6

Y1 - 2002/12/6

N2 - Let G be a graph with n vertices and minimum degree at least n/2, and B a set of vertices with at least 3n/4 vertices. In this paper, we show that there exists a hamiltonian cycle in which every vertex in B is adjacent to some vertex in B.

AB - Let G be a graph with n vertices and minimum degree at least n/2, and B a set of vertices with at least 3n/4 vertices. In this paper, we show that there exists a hamiltonian cycle in which every vertex in B is adjacent to some vertex in B.

KW - A minimum degree

KW - Dirac-type condition

KW - Hamiltonian cycles

KW - Specifed vertices

UR - http://www.scopus.com/inward/record.url?scp=0037032973&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0037032973&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(02)00263-7

DO - 10.1016/S0012-365X(02)00263-7

M3 - Article

AN - SCOPUS:0037032973

SN - 0012-365X

VL - 258

SP - X85-91

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

On a hamiltonian cycle in which specified vertices are not isolated

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this