0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Presumably for the lower bound you just need an asymptotic result?! $\endgroup$
    – Igor Rivin
    Commented Aug 22, 2016 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 Dougherty
    Commented Aug 22, 2016 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
    Commented Aug 22, 2016 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
    Commented Aug 22, 2016 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 Dougherty
    Commented Aug 22, 2016 at 8:30

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .