|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
Eric Weisstein's World of Mathematics, King Graph.
|
|
FORMULA
|
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
|
|
|
STATUS
|
approved
|
|
|
|