✦ LIBER ✦

Distributing vertices on Hamiltonian cycles

✍ Scribed by Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson; Colton Magnant

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 195 KB
Volume: 69
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20564

No coin nor oath required. For personal study only.

✦ Synopsis

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 distance along H between any two vertices of X is at least n/2__t__. In this article, minimum degree and connectivity conditions are determined such that for any graph G of sufficiently large order n and for any set of t vertices X⊆V(G), there is a hamiltonian cycle H so that the distance along H between any two consecutive vertices of X is approximately n/t. Furthermore, the minimum degree threshold is determined for the existence of a hamiltonian cycle H such that the vertices of X appear in a prescribed order at approximately predetermined distances along H. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 28–45, 2012

📜 SIMILAR VOLUMES

On a Hamiltonian Cycle in Which Specifie

On a Hamiltonian Cycle in Which Specified Vertices Are Uniformly Distributed

✍ Atsushi Kaneko; Kiyoshi Yoshimoto 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 191 KB

Let G be a graph with n vertices and minimum degree at least nÂ2, and let d be a positive integer such that d nÂ4. We define a distance between two vertices as the number of edges of a shortest path joining them. In this paper, we show that, for any vertex subset A with at most nÂ2d vertices, there

A Remark on Hamiltonian Cycles

✍ Vu-Dinh-Hoa 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 309 KB

## 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__ −

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

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 hamiltonian cycles in the prism over

On hamiltonian cycles in the prism over the odd graphs

✍ Letícia R. Bueno; Peter Horák 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 2 views

The Kneser graph K (n, k) has as its vertex set all k-subsets of an n-set and two k-subsets are adjacent if they are disjoint. The odd graph O k is a special case of Kneser graph when n = 2k +1. A long standing conjecture claims that O k is hamiltonian for all k>2. We show that the prism over O k is