Timeline for 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 + ...$
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 16, 2020 at 19:25 | comment | added | Max Alekseyev | I think a general formula here does exist, but its complexity is similar to that of Jovovic's formula. | |
| S Sep 16, 2020 at 16:59 | history | suggested | JimN | CC BY-SA 4.0 |
Added math-mode around three F(x) and two G(x) and fixed a couple of words
|
| Sep 16, 2020 at 16:51 | review | Suggested edits | |||
| S Sep 16, 2020 at 16:59 | |||||
| Mar 11, 2020 at 14:27 | history | edited | JaberMac | CC BY-SA 4.0 |
added 167 characters in body
|
| Feb 23, 2020 at 0:21 | comment | added | Brendan McKay | I agree with Andrew that a usable exact formula is unlikely except in special cases. An asymptotic formula for fixed $D$ would be not so difficult and perhaps it is published somewhere. | |
| Feb 22, 2020 at 18:31 | comment | added | Andrew | 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. | |
| Feb 22, 2020 at 14:14 | history | edited | JaberMac |
edited tags
|
|
| Feb 22, 2020 at 13:36 | history | edited | JaberMac | CC BY-SA 4.0 |
added 87 characters in body
|
| Feb 22, 2020 at 13:34 | comment | added | user44191 | It seems worth noting that you are counting isomorphism classes of graphs, not graphs in total. This usually makes counting harder (think, e.g., counting partitions vs ball-and-bin problems). | |
| Feb 22, 2020 at 13:30 | review | First posts | |||
| Feb 22, 2020 at 14:15 | |||||
| Feb 22, 2020 at 13:28 | history | asked | JaberMac | CC BY-SA 4.0 |