login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Array read by antidiagonals: T(m,n) is the number of vertices in the longest induced path in the grid graph P_m X P_n.
5

%I #15 Jan 27 2024 18:29:48

%S 1,2,2,3,3,3,4,5,5,4,5,6,7,6,5,6,8,9,9,8,6,7,9,11,11,11,9,7,8,11,14,

%T 14,14,14,11,8,9,12,16,17,17,17,16,12,9,10,14,18,20,21,21,20,18,14,10,

%U 11,15,20,22,24,24,24,22,20,15,11,12,17,22,25,27,29,29,27,25,22,17,12

%N Array read by antidiagonals: T(m,n) is the number of vertices in the longest induced path in the grid graph P_m X P_n.

%C Equivalently, T(m,n) is the maximum number of unit squares of a snake-like polyomino in an m X n rectangle.

%H Andrew Howroyd, <a href="/A360917/b360917.txt">Table of n, a(n) for n = 1..435</a>

%H Nikolai Beluhov, <a href="https://arxiv.org/abs/2301.01152">Snake paths in king and knight graphs</a>, arXiv:2301.01152 [math.CO], 2023.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>.

%F T(m,n) = T(n,m).

%F T(m,n) = 2*m*n/3 + O(m+n) (Beluhov 2023, Proposition 3). - _Pontus von Brömssen_, May 08 2023

%e Array begins:

%e ==============================================

%e m\n| 1 2 3 4 5 6 7 8 9 10 11 12 ...

%e -----+----------------------------------------

%e 1 | 1 2 3 4 5 6 7 8 9 10 11 12 ...

%e 2 | 2 3 5 6 8 9 11 12 14 15 17 18 ...

%e 3 | 3 5 7 9 11 14 16 18 20 22 24 26 ...

%e 4 | 4 6 9 11 14 17 20 22 25 28 30 33 ...

%e 5 | 5 8 11 14 17 21 24 27 30 34 37 40 ...

%e 6 | 6 9 14 17 21 24 29 32 36 40 44 47 ...

%e 7 | 7 11 16 20 24 29 33 38 42 46 50 55 ...

%e 8 | 8 12 18 22 27 32 38 42 48 52 57 62 ...

%e 9 | 9 14 20 25 30 36 42 48 53 58 64 70 ...

%e 10 | 10 15 22 28 34 40 46 52 58 64 71 77 ...

%e 11 | 11 17 24 30 37 44 50 57 64 71 77 86 ...

%e 12 | 12 18 26 33 40 47 55 62 70 77 86 92 ...

%e ...

%Y Main diagonal is A331968.

%Y Cf. A360199, A360915, A360916 (maximum induced paths), A360920.

%K nonn,tabl

%O 1,2

%A _Andrew Howroyd_, Feb 26 2023