OFFSET
1,4
COMMENTS
T(m,n) is defined as follows:
T(m, n) = T(n, m).
T(1, n) = floor(n^2/2) - 1.
T(2, n) = (n+1)^2 - 4.
For m, n >= 3 we have:
T(m, n) = m*n*(m + n)/2 - 3, if m and n are both even;
= m*n*(m + n)/2 - (m + n)/2 - 1, if m and n are both odd;
= m*n*(m + n)/2 - n/2 - 1, if m is odd and n is even.
The disorder number M(G) of a graph G is defined to be the maximal length of a walk along the edges of the graph, according to any ordering of its vertices.
Conjecture: T(m, n) = M(P_m X P_n) where P_m X P_n is the grid graph of size m X n.
The conjecture is proved if m = 1 or n = 1.
REFERENCES
L. Bulteau, S. Giraudo and S. Vialette, Disorders and Permutations, CPM, 2021.
LINKS
Sela Fried, The disorder number of a graph, arXiv:2208.03788 [math.CO], 2022.
EXAMPLE
m\n 1 2 3 4 5 6 ...
1 0 1 3 7 11 17
2 1 5 12 21 32 45
3 3 12 23 39 55 77
4 7 21 39 61 87 117
5 11 32 55 87 119 161
6 17 45 77 117 161 213
...
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Sela Fried, Aug 16 2022
STATUS
approved