

A332044


a(n) is the length of the shortest circuit that visits every edge of an undirected n X n grid graph.


0



4, 16, 28, 48, 68, 96, 124, 160, 196, 240, 284, 336, 388, 448, 508, 576, 644, 720, 796, 880, 964, 1056, 1148, 1248, 1348, 1456, 1564, 1680, 1796, 1920, 2044, 2176, 2308, 2448, 2588, 2736, 2884, 3040, 3196, 3360, 3524, 3696, 3868, 4048, 4228, 4416, 4604, 4800, 4996, 5200
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,1


COMMENTS

An n X n grid graph has a total of 2n(n1) edges. However, this results in 4n8 odd vertices, which (except in the case of n=2) means an Eulerian circuit is not possible. Each side of the graph contains n2 odd vertices.
When n is even, these vertices can be separated into pairs, and the shortest postman circuit can be created using the edges between each pair twice. This results in an increase of (n2)/2 edges per side, or an increase of 2(n2) total. When added to the total number of edges, this becomes 2n(n1) + 2(n2) = 2n^24.
When n is odd, an even number of vertices per side can be separated into pairs, with the edge between them being used twice, just as before (resulting in an increase of (n3)/2 edges per side, or an increase of 2(n3) total). However, this will leave four lone vertices  one per side. These can also be paired, and connected with two edges, for an additional 4 edges. Adding all these edges together results in 2n(n1) + 2(n3) + 4 = 2n^22.
The different forms for an even value of n and an odd value of n can be combined into a(n) = 2*n^2  4 + 2*(n mod 2).


LINKS

Table of n, a(n) for n=2..51.
Wikipedia, Eulerian path
Index entries for linear recurrences with constant coefficients, signature (2,0,2,1).


FORMULA

a(n) = 2*n^2  4 + 2*(n mod 2).
From Stefano Spezia, Feb 05 2020: (Start)
O.g.f.: 4*x^2*(1  2*x + x^2)/((1 + x)^3*(1 + x)).
E.g.f.: 4  exp(x) + exp(x)*(3 + 2*x + 2*x^2).
a(n) = 2*a(n1)  2*a(n3) + a(n4) for n > 5.
a(2*n+1) = A035008(n).
(End)


MATHEMATICA

Array[2 #^2  4 + 2 Boole[OddQ@ #] &, 51] (* Michael De Vlieger, Feb 08 2020 *)


CROSSREFS

Cf. A035008.
Sequence in context: A017569 A161335 A121054 * A273368 A209979 A294629
Adjacent sequences: A332041 A332042 A332043 * A332045 A332047 A332048


KEYWORD

nonn


AUTHOR

Stephen R Simons, Feb 05 2020


STATUS

approved



