login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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(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

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(n-1) - 2*a(n-3) + a(n-4) 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 3 01:31 EDT 2020. Contains 333195 sequences. (Running on oeis4.)