A332044 - OEIS

%I #31 Sep 10 2021 13:23:44

%S 4,16,28,48,68,96,124,160,196,240,284,336,388,448,508,576,644,720,796,

%T 880,964,1056,1148,1248,1348,1456,1564,1680,1796,1920,2044,2176,2308,

%U 2448,2588,2736,2884,3040,3196,3360,3524,3696,3868,4048,4228,4416,4604,4800,4996,5200

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

%C 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.

%C 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.

%C 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.

%C 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).

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Eulerian_path">Eulerian path</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-2,1).

%F a(n) = 2*n^2 - 4 + 2*(n mod 2).

%F From _Stefano Spezia_, Feb 05 2020: (Start)

%F O.g.f.: 4*x^2*(-1 - 2*x + x^2)/((-1 + x)^3*(1 + x)).

%F E.g.f.: 4 - exp(-x) + exp(x)*(-3 + 2*x + 2*x^2).

%F a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4) for n > 5.

%F a(2*n+1) = A035008(n).

%F (End)

%t Array[2 #^2 - 4 + 2 Boole[OddQ@ #] &, 51] (* _Michael De Vlieger_, Feb 08 2020 *)

%t LinearRecurrence[{2,0,-2,1},{4,16,28,48},50] (* _Harvey P. Dale_, Sep 10 2021 *)

%Y Cf. A035008.

%K nonn

%O 2,1

%A _Stephen R Simons_, Feb 05 2020