A382665 Number of distinct degree sequences among all connected simple graphs with n vertices whose degrees are consecutive integers.

1, 1, 1, 2, 5, 14, 35, 88, 212, 492, 1122

Offset: 0

Author

John P. McSorley, Apr 02 2025

Keywords

• nonn
• more

Comments

A sequence of integers is consecutive if its distinct entries are consecutive integers, and a graphic sequence is a sequence of integers that is the degree sequence of some graph. Thus a(n) is the number of graphic sequences of length n that are consecutive and represent a connected graph.

Examples

			For n = 5 there are 21 non-isomorphic connected graphs G on 5 vertices, and 16 of these have a consecutive degree sequence. However consecutive degree sequences 12223, and 22233 each correspond to 2 non-isomorphic connected graphs. Thus there are 14 distinct graphic sequences of length 5 that are consecutive and represent a connected graph, and so a(5)=14.
		

References

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

Crossrefs

Cf. A001349, A381765, A382021.

Extensions

a(7)-a(10) from Andrew Howroyd, Apr 02 2025