There have been many questions on this site about counting non-isormorphic graphs that are (1) strongly regular, (2) have a certain chromatic number, (3) connected, among many others.

What work has been done to count the number of non-isomorphic graphs that are connected and spanning that have exactly $n$ vertices and $m$ edges? Clearly, for $m < n-1$, this number is 0, and for $m = n-1$, this is the number of non-isomorphic spanning trees on $n$ vertices, which already does not seem to have a closed-form formula. However, this becomes even more complicated for larger values of $m$ (although there are some partial results for some graph classes with $m = n-1$ here).

If there is not a single expression (either recursive, or composed of a few "ingredients"), are there graph classes for which the number is known? This is helpful in determining an upper bound on the number of distinct reliability polynomials on graphs with $n$ vertices, $m$ edges.

  • $\begingroup$ Presumably for the lower bound you just need an asymptotic result?! $\endgroup$ – Igor Rivin Aug 22 '16 at 1:55
  • $\begingroup$ @IgorRivin asymptotics would help but I was wondering if explicit formulas/values were known for certain graph classes. I haven't found any for specifically non-isomorphic connected spanning graphs, only for a subset of these. $\endgroup$ – Ryan Aug 22 '16 at 2:32
  • 1
    $\begingroup$ You are using the word "spanning" in a non-standard fashion. Normally it is only used to indicate that a subgraph includes every vertex of the supergraph, not as a property of one graph alone. The case $m=n$ is at oeis.org/A001429 . $\endgroup$ – Brendan McKay Aug 22 '16 at 5:37
  • 1
    $\begingroup$ $m=n+1$ at oeis.org/A001435, $m=n+2$ at oeis.org/A001436 . In general Polya theory can provide these numbers but there is no simple explicit formula. $\endgroup$ – Brendan McKay Aug 22 '16 at 5:43
  • $\begingroup$ @DouglasZare You are right, I meant upper bounds. Isomorphic graphs obviously have the same reliability polynomial, and there are non-isomorphic graph cases that have the same one also. So there are fewer reliability polynomials than the # of non-isomorphic graph classes (obviously on a fixed number of vertices/edges). $\endgroup$ – Ryan Aug 22 '16 at 8:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.