A165143 -id:A165143 - cp's OEIS frontend

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

Pontus von Brömssen, Oct 01 2022

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

			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 .

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.

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

Cf. A000982, A165143, A357357, A361171.

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)

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

A357500 Largest number of nodes of an induced path in the n X n knight graph.

Original entry on oeis.org

1, 1, 7, 9, 15, 21, 24, 34

Offset: 1

Pontus von Brömssen, Oct 01 2022

			Longest paths for 3 <= n <= 7:
  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 X
                                              X X . X X . .

Thomas Dawson, Échecs Féeriques, L'Échiquier, volume 2, issue 2, 1930; issue 3, 1931.
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.

Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023.
Eric Weisstein's World of Mathematics, Knight Graph.
Wikipedia, Induced path

Cf. A165143, A331968.

a(n) >= A165143(n) - 1 for n >= 3.
a(n) <= (4*(n^2+3*n-2)-1)/7 for n >= 4. - Elijah Beregovsky, Dec 22 2022
a(n) = n^2/2 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions