A357501 - OEIS

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

(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

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;