Premium
A Remark on Hamiltonian Cycles
Author(s) -
Vu-Dinh-Hoa
Publication year - 1992
Publication title -
mathematische nachrichten
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.913
H-Index - 50
eISSN - 1522-2616
pISSN - 0025-584X
DOI - 10.1002/mana.19921570112
Subject(s) - mathematics , combinatorics , independence number , graph , undirected graph , hamiltonian (control theory) , quartic graph , hamiltonian path , discrete mathematics , graph power , simple graph , line graph , mathematical optimization
Abstract Let G be an undirected and simple graph on n vertices. Let ω, α and χ denote the number of components, the independence number and the connectivity number of G. G is called a 1‐tough graph if ω( G – S ) ⩽ | S | for any subset S of V ( G ) such that ω( G − S ) > 1. Let σ 2 = min { d ( v ) + d ( w )| v and w are nonadjacent}. Note that the difference α ‐ χ in 1‐tough graph may be made arbitrary large. In this paper we prove that any 1‐tough graph with σ 2 > n + χ ‐ α is hamiltonian.