Skip to main content
Andrew's user avatar
Andrew's user avatar
Andrew's user avatar
Andrew
  • Member for 4 years, 10 months
  • Last seen more than 4 years ago
comment
What is the number of connected graphs with $n$ vertices of max. degree up to $D$? Leaving $F(x) = x + x^2 + 2x^3 + 6x^4 + 21x^5 + 112x^6 + ...$
There is unlikely to be a formula as such, although as noted by others it can be computed from the values for not necessarily connected graphs. (See A263293 in OEIS for values up to 10 nodes - these values were obtained by brute force enumeration of all graphs). Better methods exist, since it isn't necessary to enumerate every graph - only every degree sequence, but to my knowledge this has not been done. This technique, might give values up to about 15 nodes, but it is still exponential.