Name
Abstract | ||
|---|---|---|
The digraphs P(n, k) have vertices corresponding to length k permutations of an n set and arcs corresponding to (k + 1) permutations. Answering a question of Starling, Klerlein, Kier and Carr we show that these digraphs are Hamiltonian for k ≤ n - 3. We do this using restricted Eulerian cycles and the fact that P(n, k) is nearly the line digraph of P(n, k - 1). We also show that the digraphs P(n, n - 2) are not Hamiltonian for n ≥ 4 using a result of Rankin on Cayley digraphs. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.ejc.2005.05.007 | Eur. J. Comb. |
Keywords | Field | DocType |
universal cycle,line digraph,n set,eulerian cycle,cayley digraph,digraphs p,length k permutation | Discrete mathematics,Combinatorics,Vertex (geometry),Hamiltonian (quantum mechanics),Permutation,Cayley digraphs,Eulerian path,Mathematics,Digraph | Journal |
Volume | Issue | ISSN |
27 | 6 | 0195-6698 |
Citations | PageRank | References |
3 | 0.45 | 5 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Garth Isaak | 1 | 172 | 24.01 |