

A332044


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


1



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



FORMULA

a(n) = 2*n^2  4 + 2*(n mod 2).
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.
(End)


MATHEMATICA

LinearRecurrence[{2, 0, 2, 1}, {4, 16, 28, 48}, 50] (* Harvey P. Dale, Sep 10 2021 *)


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



