A329910 Number of harmoniously labeled graphs with n edges and at most n vertices.

0, 0, 1, 4, 32, 72, 2187, 20736, 262144, 3200000, 48828125, 729000000, 13060694016, 230539333248, 4747561509943, 96717311574016, 2251799813685250, 51998697814229000, 1350851717672990000, 34867844010000000000, 1000000000000000000000, 28531167061100000000000

Offset

1,4

Comments

A graph G with n edges is harmonious if there is an injection f from its vertex set to the group of integers modulo n such that when each edge uv of G is assigned the weight f(u)+f(v) (mod n), the resulting weights are distinct.

Links

Table of n, a(n) for n=1..22.

R. L. Graham and N. J. A. Sloane, On Additive Bases and Harmonious Graphs, SIAM J. Algebraic and Discrete Methods, 1 (1980), 382-404.

R. L. Graham and N. J. A. Sloane, On Additive Bases and Harmonious Graphs

Formula

For n odd, a(n) = ((n-1)/2)^n. For n even, a(n) = (n*(n-2)/4)^(n/2).

Example

a(3)=1 because there is only one harmonious graph with 3 edges and at most 3 vertices.

Mathematica

Table[If[EvenQ[n], (n*(n-2)/4)^(n/2), ((n-1)/2)^n], {n, 1, 22}] (* Stefano Spezia, Nov 24 2019 *)

Crossrefs

A085526 contains the odd-indexed terms.

Sequence in context: A076137 A138340 A113250 * A012036 A153794 A222326

Adjacent sequences: A329907 A329908 A329909 * A329911 A329912 A329913

Keyword

nonn,easy

Author

Christian Barrientos, Nov 23 2019

Status

approved