The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A354568 Irregular triangle read by rows: T(n,k) is the number of Hamiltonian cycles in the Kneser graph K(n,k), 1 <= k < n/2. 0
 1, 3, 12, 0, 60, 155328 (list; graph; refs; listen; history; text; internal format)
 OFFSET 3,2 COMMENTS It has been conjectured that T(n,k) > 0 (i.e., that K(n,k) is Hamiltonian) for all 1 <= k < n/2, with the exception (n,k) = (5,2) (the Petersen graph). See Lovász 1970 for a more general conjecture. It is known that T(n,k) > 0 in the following cases: if n >= (3*k+1+sqrt(5*k^2-2*k+1))/2 (Chen 2003); if n <= 27, with the exception (n,k) = (5,2) (see Shields and Savage 2004); if k >= 3 and n-2*k is a power of 2 (Mütze, Nummenpalo, and Walczak 2018). REFERENCES László Lovász, Problem 11 in: Richard K. Guy (editor), Combinatorial Structures and Their Applications, Gordon and Breach 1970. LINKS Table of n, a(n) for n=3..8. Ya-Chen Chen, Triangle-free Hamiltonian Kneser graphs, Journal of Combinatorial Theory, Series B 89 (2003), 1-16. Torsten Mütze, Jerri Nummenpalo, and Bartosz Walczak, Sparse Kneser graphs are Hamiltonian, STOC'18 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing 2018, 912-919. Ian Shields and Carla D. Savage, A note on Hamilton cycles in Kneser graphs, Bulletin of the Institute of Combinatorics and Its Applications 40 (2004), 13-22. Wikipedia, Kneser graph. FORMULA T(n,1) = (n-1)!/2 = A001710(n-1) for n >= 3. T(2*k+1,k) >= 2^2^(k-6) for k >= 6. (Mütze, Nummenpalo, and Walczak 2018). EXAMPLE Triangle begins: n\k| 1 2 ---+---------- 3 | 1 4 | 3 5 | 12 0 6 | 60 155328 CROSSREFS Cf. A001710, A301560. Sequence in context: A101710 A088799 A181405 * A072117 A162853 A162854 Adjacent sequences: A354565 A354566 A354567 * A354569 A354570 A354571 KEYWORD nonn,tabf,more AUTHOR Pontus von Brömssen, Aug 18 2022 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 1 05:26 EST 2023. Contains 367468 sequences. (Running on oeis4.)