Triangle-free Hamiltonian Kneser graphs

被引：27

作者：

Chen, YC ^{[1
]}

机构：

[1] Arizona State Univ, Dept Math, Tempe, AZ 85287 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2003年 / 89卷 / 01期

关键词：

Hamiltonian cycles; uniform subset graphs; antipodal layers problem; Kneser graphs;

D O I：

10.1016/S0095-8956(03)00040-6

中图分类号：

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-sets are disjoint. When n<3k, the Kneser Graph K(n,k) has no triangle. In this paper, we prove that K(n, k) is Hamiltonian for ngreater than or equal to(3k + 1 + root5k(2) - 2k + 1)/2, and extend this to the bipartite Kneser graphs. Note that (3k + 1 + root5k(2) - 2k + 1)/2 < 2.62k + 1. (C) 2003 Elsevier Science (USA). All rights reserved.

引用

页码：1 / 16

页数：16

共 20 条

[1]

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

[2] HAMILTONIAN UNIFORM SUBSET GRAPHS [J].