Kneser graphs are Hamiltonian for n ≥ 3k

被引：32

作者：

Chen, YC ^{[1
]}

机构：

[1] Univ Illinois, Dept Math, Urbana, IL 61801 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2000年 / 80卷 / 01期

关键词：

Hamiltonian cycles; uniform subset graphs; antipodal layers problem; Kneser graphs; Gray codes; Erdos revolving door problem;

D O I：

10.1006/jctb.2000.1969

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 it n greater than or equal to 3k, and extend this to the bipartite Kneser graphs. (C) 2000 Academic Press.

引用

页码：69 / 79

页数：11

共 17 条

[1]

Baranyai Zs., 1975, C MATH SOC JANOS BOL, V10, P91

[2] HAMILTONIAN UNIFORM SUBSET GRAPHS [J].