A357501 Length of longest induced cycle in the n X n king graph.

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

Table of n, a(n) for n=1..17.

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

Cf. A000982, A165143, A357357, A361171.

Sequence in context: A190158 A188217 A138926 * A085635 A077434 A076136

Adjacent sequences: A357498 A357499 A357500 * A357502 A357503 A357504

Keyword

nonn,more

Author

Pontus von Brömssen, Oct 01 2022

Extensions

a(9)-a(17) from Andrew Howroyd, Mar 03 2023

Status

approved