A395104 Number of alpha-labelings of the path tree on n vertices.

1, 1, 2, 2, 2, 4, 8, 4, 10, 28, 36, 64, 112, 200, 496, 888, 1778, 3644, 9644, 18384, 35244, 88512, 240912, 490496, 1068256, 2898384, 8330688, 18072064, 42690600, 119723792, 362082648, 837947696, 2118951762, 6211260556, 19630042716, 48172034512, 128288363220, 392572281584

Offset

1,3

Comments

A labeling of a tree on n vertices is called an alpha-labeling if it is a graceful labeling with the additional property that there exists a critical value k such that for every edge u--v, one endpoint has label <= k and the other has label > k.

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

Links

Bert Dobbelaere, Table of n, a(n) for n = 1..55

Igor Blokhin, Graph Theory (Python repository).

A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (International Symposium, Rome, 1966), Gordon and Breach, 1967, pp. 349-355.

David A. Sheppard, The factorial representation of balanced labelled graphs, Discrete Math., 15 (1976), no. 4, 379-388.

Example

For example, consider the path graph on 4 vertices. The labeling 0--3--1--2 is graceful since the induced edge labels are |0-3|=3, |3-1|=2, |1-2|=1, giving {1,2,3}. Moreover, it is an alpha-labeling: taking k=1, the vertices are split into {0,1} and {2,3}, and every edge has one endpoint in each part.

Crossrefs

Cf. A112362, A005193, A392797.

Sequence in context: A244458 A286613 A229061 * A339464 A278224 A161421

Adjacent sequences: A395101 A395102 A395103 * A395105 A395106 A395107

Keyword

nonn,hard

Author

Igor Blokhin, Apr 11 2026

Extensions

More terms from Bert Dobbelaere, Apr 19 2026

Status

approved