✦ LIBER ✦

A Remark on Hamiltonian Cycles

✍ Scribed by Vu-Dinh-Hoa

Publisher: John Wiley and Sons
Year: 1992
Tongue: English
Weight: 309 KB
Volume: 157
Category: Article
ISSN: 0025-584X
DOI: 10.1002/mana.19921570112

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Distributing vertices on Hamiltonian cyc

Distributing vertices on Hamiltonian cycles

✍ Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson; Colton Magnant 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 195 KB

## Abstract Let __G__ be a graph of order __n__ and 3≤__t__≤__n__/4 be an integer. Recently, Kaneko and Yoshimoto [J Combin Theory Ser B 81(1) (2001), 100–109] provided a sharp δ(__G__) condition such that for any set __X__ of __t__ vertices, __G__ contains a hamiltonian cycle __H__ so that the dis

On certain Hamiltonian cycles in planar

On certain Hamiltonian cycles in planar graphs

✍ B�hme, T.; Harant, J.; Tk�?, M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB 👁 2 views

The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that mus

A Matrix Method for Counting Hamiltonian

A Matrix Method for Counting Hamiltonian Cycles on Grid Graphs

✍ Y.H.Harris Kwong; D.G. Rogers 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 154 KB

A matrix method is used to determine the number of Hamiltonian cycles on \(P_{m} \times P_{n}, m=4\), 5. This provides an alternative to other approaches which had been used to solve the problem. The method and its more generalized version, transfer-matrix method, may give easier solutions to cases

On the number of Hamiltonian cycles in t

On the number of Hamiltonian cycles in triangulations

✍ Jan Kratochvil; Dainis Zeps 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB 👁 2 views

It is proved that if a planar triangulation different from K3 and K4 contains a Hamiltonian cycle, then it contains at least four of them. Together with the result of Hakimi, Schmeichel, and Thomassen [21, this yields that, for n 2 12, the minimum number of Hamiltonian cycles in a Hamiltonian planar

Hamiltonian cycles in bipartite quadrang

Hamiltonian cycles in bipartite quadrangulations on the torus

✍ Atsuhiro Nakamoto; Kenta Ozeki 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 133 KB 👁 2 views

## Abstract In this article, we shall prove that every bipartite quadrangulation __G__ on the torus admits a simple closed curve visiting each face and each vertex of __G__ exactly once but crossing no edge. As an application, we conclude that the radial graph of any bipartite quadrangulation on th

On the Approximation of Finding A(nother

On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs

✍ Cristina Bazgan; Miklos Santha; Zsolt Tuza 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 144 KB

It is a simple fact that cubic Hamiltonian graphs have at least two Hamiltonian cycles. Finding such a cycle is NP-hard in general, and no polynomial-time algorithm is known for the problem of finding a second Hamiltonian cycle when one such cycle is given as part of the input. We investigate the co