A381765 Number of connected simple graphs on n unlabeled vertices whose degree sequence is consecutive.

1, 1, 1, 2, 5, 16, 75, 544, 6920, 159228, 6961507, 577826609, 90529308665

Offset

0,4

Comments

A connected graph has a consecutive degree sequence if its distinct degrees are consecutive integers. This includes all connected regular graphs.

References

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford University Press (1999).

Links

Table of n, a(n) for n=0..12.

Example

For n = 4 there are 6 non-isomorphic connected graphs G on 4 vertices. An example with consecutive degree sequence is P_4, the path on 4 vertices, with degree sequence 1122; and an example with non-consecutive degree sequence is the star K_{1,3} with degree sequence 1113. All other connected G have consecutive degree sequence. Thus a(4) = 5.

Crossrefs

Cf. A381586, A001349, A005177.

Sequence in context: A002632 A020127 A179500 * A377569 A121396 A371829

Adjacent sequences: A381762 A381763 A381764 * A381766 A381767 A381768

Keyword

nonn,more

Author

John P. McSorley, Mar 25 2025

Extensions

a(7)-a(10) from Andrew Howroyd, Mar 26 2025

a(11)-a(12) from Sean A. Irvine, Apr 01 2025

Status

approved