✦ LIBER ✦

k-ordered Hamiltonian graphs

✍ Scribed by Ng, Lenhard; Schultz, Michelle

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 144 KB
Volume: 24
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199701)24:1<45::aid-jgt6>3.0.co;2-j

No coin nor oath required. For personal study only.

✦ Synopsis

A hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v 1 , v 2 , . . . , v k of k distinct vertices of G, there exists a hamiltonian cycle that encounters v 1 , v 2 , . . . , v k in this order. Theorems by Dirac and Ore, presenting sufficient conditions for a graph to be hamiltonian, are generalized to k-ordered hamiltonian graphs. The existence of k-ordered graphs with small maximum degree is investigated; in particular, a family of 4-regular 4-ordered graphs is described. A graph G of order n ≥ 3 is k-hamiltonian-connected, 2 ≤ k ≤ n, if for every sequence v 1 , v 2 , . . . , v k of k distinct vertices, G contains a v 1 -v k hamiltonian path that encounters v 1 , v 2 , . . . , v k in this order. It is shown that for k ≥ 3, every (k +1)-hamiltonian-connected graph is k-ordered and a result of Ore on hamiltonian-connected graphs is generalized to k-hamiltonian-connected graphs.

📜 SIMILAR VOLUMES

Onk-ordered Hamiltonian graphs

✍ Kierstead, H. A.; S�rk�zy, G. N.; Selkow, S. M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB 👁 1 views

the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine

On k-ordered graphs

✍ Jill R. Faudree; Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson; Linda L 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB

Hamiltonian ?-factors in graphs

✍ Wei, Bing; Zhu, Yongjin 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB 👁 2 views

Let k ≥ 2 be an integer. A k-factor F of a graph G is called a hamiltonian k-factor if F contains a hamiltonian cycle. In this paper, we shall prove that if G is a graph of order n with k ≥ 2, n ≥ 8k -4, kn even and δ(G) ≥ n/2, then G has a hamiltonian k-factor.

Hamiltonian-laceability of star graphs

✍ Sun-Yuan Hsieh; Gen-Huey Chen; Chin-Wen Ho 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB 👁 1 views

Tough enough chordal graphs are Hamilton

Tough enough chordal graphs are Hamiltonian

✍ Chen, Guantao; Jacobson, Michael S.; K�zdy, Andr� E.; Lehel, Jen? 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB 👁 2 views

We prove that every 18-tough chordal graph has a Hamiltonian cycle.

Powers of Hamiltonian paths in interval

Powers of Hamiltonian paths in interval graphs

✍ Isaak, Garth 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 232 KB 👁 1 views

We give a simple proof that the obvious necessary conditions for a graph to contain the k th power of a Hamiltonian path are sufficient for the class of interval graphs. The proof is based on showing that a greedy algorithm tests for the existence of Hamiltonian path powers in interval graphs. We wi