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

Author

John P. McSorley, Mar 25 2025

Keywords

• nonn
• more

Comments

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

Examples

			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.
		

References

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

Crossrefs

Cf. A381586, A001349, A005177.

Extensions

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

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