login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A357501
Length of longest induced cycle in the n X n king graph.
3
0, 3, 4, 8, 12, 16, 24, 31, 38, 47, 60, 71, 82, 95, 112, 127, 142
OFFSET
1,2
COMMENTS
The largest number of nodes of an induced path (instead of cycle) in the n X n king graph is A000982(n) = ceiling(n^2/2) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023
REFERENCES
Donald E. Knuth, The Art of Computer Programming, Volume 4B, Combinatorial Algorithms, Part 2, Addison-Wesley, 2023. See exercise 7.2.2.1-172 and its solution.
LINKS
Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023.
Eric Weisstein's World of Mathematics, King Graph.
Wikipedia, Induced path
FORMULA
From Pontus von Brömssen, Jan 30 2023: (Start)
Beluhov (2023) proves that
a(n) = n^2/2-1 if n == 0 (mod 4) and n >= 8;
a(n) = (n^2-1)/2 if n == 3 (mod 4);
and says that experimental data suggests that perhaps
a(n) = (n^2-5)/2 if n == 1 (mod 4) and n >= 13;
a(n) = n^2/2-3 if n == 2 (mod 4) and n >= 14.
(End)
EXAMPLE
Longest induced cycles for 6 <= n <= 8:
. X X X X . . X X X X X . . X X X X X X .
X . . . . X X . . . . . X X . . . . . . X
X . . . . X X . . X . . X X . . X X . . X
X . . . . X X . X . X . X X . X . . X . X
X . . . . X X . X . X . X X . . X . X . X
. X X X X . X . X . X . X X . . X . X . X
. X . . . X . X . . X . X . X
. X X . . . X .
CROSSREFS
KEYWORD
nonn,more
AUTHOR
EXTENSIONS
a(9)-a(17) from Andrew Howroyd, Mar 03 2023
STATUS
approved