✦ LIBER ✦

Degree conditions for k-ordered hamiltonian graphs

✍ Scribed by Ralph J. Faudree; Ronald. J. Gould; Alexandr V. Kostochka; Linda Lesniak; Ingo Schiermeyer; Akira Saito

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 113 KB
Volume: 42
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10084

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For a positive integer k, a graph G is k‐ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. It is shown that if G is a graph of order n with 3 ≤ k ≤ n/2, and deg(u) + deg(v) ≥ n + (3__k__ − 9)/2 for every pair u, v of nonadjacent vertices of G, then G is k‐ordered hamiltonian. Minimum degree conditions are also given for k‐ordered hamiltonicity. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 199–210, 2003

📜 SIMILAR VOLUMES

k-ordered Hamiltonian graphs

✍ Ng, Lenhard; Schultz, Michelle 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 2 views

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 h

One sufficient condition for hamiltonian

One sufficient condition for hamiltonian graphs

✍ Guantao Chen 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 220 KB 👁 1 views

## Abstract Let __G__ be a 2‐connected graph of order __n.__ We show that if for each pair of nonadjacent vertices __x__,__y__ ∈ __V(G)__, then __G__ is Hamiltonian.

A new sufficient condition for hamiltoni

A new sufficient condition for hamiltonian graphs

✍ Pierre Fraisse 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB 👁 1 views

Sufficient degree conditions for k-edge-

Sufficient degree conditions for k-edge-connectedness of a graph

✍ D. Bauer; S.L. Hakimi; N. Kahl; E. Schmeichel 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 83 KB

Kneser Graphs Are Hamiltonian For n⩾3k

✍ Ya-Chen Chen 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 168 KB

The Kneser graph K(n, k) has as vertices the k-subsets of [1, 2, ..., n]. Two vertices are adjacent if the k-subsets are disjoint. In this paper, we prove that K(n, k) is Hamiltonian for n 3k, and extend this to the bipartite Kneser graphs.

A degree condition for the circumference

A degree condition for the circumference of a graph

✍ Nathaniel Dean; Pierre Fraisse 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 1 views

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let rn be any positive integer. Suppose G is a 2-connected graph with vertices x,, . . . , x, and edge set E that satisfies the proper