A394464 Number of graceful Prüfer codes on n vertices whose tree is the path graph and whose last element equals 0.

1, 3, 8, 10, 14, 42, 94, 200, 430, 1026, 3208, 8282, 17982, 46332, 164230, 468100, 1125394, 3366910, 12419216, 38282268, 101471130, 326653640, 1275804912, 4237867810, 12181603724

Offset

4,2

Comments

Any labeled tree on n vertices admits a unique Prüfer code. A graceful labeling of a tree on n vertices assigns the labels {0,1,...,n-1} to the vertices such that the induced edge labels (absolute differences of endpoint labels) are exactly {1,2,...,n-1}.

A path graph on n vertices is a tree with exactly two vertices of degree 1 and all other vertices of degree 2.

References

Douglas B. West, Introduction to Graph Theory, Pearson Education Pte. Ltd, 2002, page 81.

Links

Table of n, a(n) for n=4..28.

Igor Blokhin, Graph Theory (Python repository).

Formula

For n>=4: a(n) = A112362(n) - A394465(n).

Example

a(4)=1, meaning that among all graceful Prüfer codes (of length 2) of path graph on vertices {0,1,2,3}, there are 1 code ending in 0: (2, 0). This code correspond to the graph 1--2--0--3.

Crossrefs

Cf. A112362, A394465.

Sequence in context: A003038 A184870 A073547 * A047356 A083246 A023492

Adjacent sequences: A394461 A394462 A394463 * A394465 A394466 A394467

Keyword

nonn,hard,more

Author

Igor Blokhin, Mar 21 2026

Extensions

a(15) from Igor Blokhin, Mar 31 2026

a(16)-a(28) from Bert Dobbelaere, Apr 19 2026

Status

approved