✦ LIBER ✦

Kneser Graphs Are Hamiltonian For n⩾3k

✍ Scribed by Ya-Chen Chen

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 168 KB
Volume: 80
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.1969

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Degree conditions for k-ordered hamilton

Degree conditions for k-ordered hamiltonian graphs

✍ Ralph J. Faudree; Ronald. J. Gould; Alexandr V. Kostochka; Linda Lesniak; Ingo S 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 113 KB 👁 1 views

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

Hamiltonian results in K1,3-free graphs

✍ M. M. Matthews; D. P. Sumner 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 357 KB 👁 1 views

There have been a number of results dealing with Hamiltonian properties in powers of graphs. In this paper we show that the square and the total graph of a K,,,-free graph are vertex pancyclic. We then discuss some of the relationships between connectivity and Hamiltonian properties in K,.3-free gra

Hamiltonian circuits in N2-locally conne

Hamiltonian circuits in N2-locally connected K1,3-free graphs

✍ ZdeněK Ryjáček 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 407 KB 👁 1 views

## Abstract There are many results concerned with the hamiltonicity of __K__~1,3~‐free graphs. In the paper we show that one of the sufficient conditions for the __K__~1,3~‐free graph to be Hamiltonian can be improved using the concept of second‐type vertex neighborhood. The paper is concluded with

3-Connected line graphs of triangular gr

3-Connected line graphs of triangular graphs are panconnected and 1-hamiltonian

✍ H. J. Broersma; H. J. Veldman 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB 👁 1 views

A graph is k-triangular if each edge is in at least k triangles. Triangular is a synonym for l-triangular. It is shown that the line graph of a triangular graph of order at least 4 is panconnected if and only if it is 3-connected. Furthermore, the line graph of a k-triangular graph is k-harniltonian

The graphs for which all strong orientat

The graphs for which all strong orientations are hamiltonian

✍ Martin Grötschel; Frank Harary 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## Abstract We show that the only nontrivial strongly orientable graphs for which every strong oreintation is Hamiltonian are complete graphs and cycles.

Claw-free 3-connected P11-free graphs ar

Claw-free 3-connected P11-free graphs are hamiltonian

✍ Tomasz Łuczak; Florian Pfender 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB 👁 2 views

## Abstract We show that every 3‐connected claw‐free graph which contains no induced copy of __P__~11~ is hamiltonian. Since there exist non‐hamiltonian 3‐connected claw‐free graphs without induced copies of __P__~12~ this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph T