Name
Abstract | ||
|---|---|---|
The Kneser graph K(n,k) has all k-subsets of an n-set as its vertices and two subsets are adjacent if they are disjoint. Lovász conjectured that every connected vertex-transitive graph has a hamiltonian path. For n⩾2k+1, the Kneser graphs form a well-studied family of connected, regular, vertex-transitive graphs. A direct computation of hamiltonian cycles in K(n,k) is not feasible for large values of k, because K(n,k) has (nk) vertices. We give a sufficient condition for K(2k+2,k) to be hamiltonian for odd k: the existence of a particular hamiltonian path in a reduced graph over K(2k+2,k). Also, we extend this result to the bipartite Kneser graphs B(2k+2,k) for odd k. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.endm.2011.05.050 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Hamiltonian cycle,hamiltonian path,Kneser graphs | Odd graph,Discrete mathematics,Combinatorics,Indifference graph,Hamiltonian path,Chordal graph,Bipartite graph,Hamiltonian path problem,Kneser graph,Mathematics,Pancyclic graph | Journal |
Volume | ISSN | Citations |
37 | 1571-0653 | 1 |
PageRank | References | Authors |
0.37 | 7 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Letícia Rodrigues Bueno | 1 | 2 | 2.42 |
| Celina M. Herrera de Figueiredo | 2 | 1 | 0.70 |
| Luerbio Faria | 3 | 133 | 20.98 |
| Candido F.X. Mendonça | 4 | 12 | 2.52 |
| Rodrigo de A. Hausen | 5 | 16 | 5.02 |