Maximal path

[hv at crypt.org]

"kohmoto" <zbi74583 at boat.zero.ad.jp> wrote:
:    I calculated "Length of maximal di-path on grid graph n x n", but it 
:already existed on OEIS.
:    It is A049486.
:         .__.__.__.__.
:         |__|__|__|__|
:         |__|__|__|__|
:         |__|__|__|__|
:         |__|__|__|__|
:
:         S_0 : 0, 4, 10, 21, 34, 53,

This is rated "hard", but it doesn't seem so bad to me: it just needs
vertex counting.

The n x n square has #(n) = 2n(n+1) line segments and v_o(n) = 4(n-1)
vertices of odd degree. The network is traversable only when v_o(n) <= 2.
When not, we must lose sufficient line segments to reduce v_o() to 2.

For odd n >= 3, we have an even number of odd vertices along each
edge; we can pair them up, and lose the single line segment joining
each pair except for our start/end points. So in this case we have
a(n) = #(n) - (v_o(n) - 2)/2 = 2n^2 + 3.

For even n >= 2, we have an odd number of odd vertices along each
edge. The best we can do is start and end at the two vertices
adjacent to one corner; pairing up the rest allows us to lose a
single line segment for each of the remaining pairs except for
the two vertices adjacent to the diagonally opposite corner, for
which we must lose 2 line segments. So in this case we have
a(n) = #(n) - ((v_o(n) - 4)/2 + 2) = 2n^2 + 2.

For n < 2, we have no vertices of odd degree, so we cannot save a
segment by starting and ending on a pair of them. So we can specify
the exact function using a couple of characteristic functions:

  a(n) = 2n^2 + 1 + c(n > 1) + c(n odd)

(I'm assuming a(0) = 1 here, on the grounds that there is a single
zero-length path in that case.)

Note that the theoretical maximum is always achievable, eg using
Fleury's algorithm.

This gives the sequence (up to a(40)):

  (0 or 1), 4, 10, 21, 34, 53, 74, 101, 130, 165, 202, 245, 290, 341, 394,
  453, 514, 581, 650, 725, 802, 885, 970, 1061, 1154, 1253, 1354, 1461, 1570,
  1685, 1802, 1925, 2050, 2181, 2314, 2453, 2594, 2741, 2890, 3045, 3202

I haven't considered your second sequence yet (number of maximal paths),
but perhaps this will help prompt directions to think about it: certainly
it should help clarify which traversable networks need to be considered.

Hugo