𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hamiltonian Kneser Graphs

✍ Scribed by Ya-Chen Chen; Z. Füredi

Book ID
106167931
Publisher
Springer-Verlag
Year
2002
Tongue
English
Weight
99 KB
Volume
22
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Kneser Graphs Are Hamiltonian For n⩾3k
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.

-coloring of Kneser graphs
-coloring of Kneser graphs
✍ R. Balakrishnan; T. Kavaskar 📂 Article 📅 2012 🏛 Elsevier Science 🌐 English ⚖ 309 KB
Kneser Representations of Graphs
Kneser Representations of Graphs
✍ Hamburger, Peter; Por, Attila; Walsh, Matt 📂 Article 📅 2009 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 203 KB
Strong products of Kneser graphs
Strong products of Kneser graphs
✍ Sandi Klavžar; Uroš Milutinović 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 314 KB

Let G [XI H be the strong product of graphs G and H. We give a short proof that Kneser graphs are then used to demonstrate that this lower bound is sharp. We also prove that for every n > 2 there is an infinite sequence of pairs of graphs G and G' such that G' is not a retract of G while G' IXI K,