|
| |
|
|
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(n-1) edges. However, this results in 4n-8 odd vertices, which (except in the case of n=2) means an Eulerian circuit is not possible. Each side of the graph contains n-2 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 (n-2)/2 edges per side, or an increase of 2(n-2) total. When added to the total number of edges, this becomes 2n(n-1) + 2(n-2) = 2n^2-4.
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 (n-3)/2 edges per side, or an increase of 2(n-3) 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(n-1) + 2(n-3) + 4 = 2n^2-2.
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(n-1) - 2*a(n-3) + a(n-4) 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
|
| |
|
|
