1
$\begingroup$

I have been trying to count the number of graphs up to isomorphism which are:

  1. Simple
  2. Connected
  3. Have $n$ edges.

I apologize in advance if there is ample documentation on this question; however, I have found none. Thus far, my best overestimate is: $$g(n) = \sum_{i=x}^y t(i) \cdot \binom{a(i)} { n - i - 1}$$

where:

$g(n) := $ the number of such graphs with $n$ edges,

$t(i) :=$ the number of trees up to isomorphism on $i$ vertices,

$a(i) :=$ the number of non-adjacent vertices in a tree on $i$ vertices.

I have conjectured that: $$a(i) = \sum_{k-1}^i (i - k), \qquad y = n+1,\quad\text{and}$$ $x \geq $ the number of vertices in the complete graph with the closest number of edges to $n$, rounded down.

I have also read that the number of trees including isomorphism with $i$ vertices is $i^{i-2}$, and have placed that as the upper bound for $t(i)$.

And that [according to Wikipedia] there is an estimate for the number of such trees up to isomorphism: $t(i)\sim C \alpha^i i^{-5/2}$ with $C=0.534949606...$ and $\alpha=2.99557658565...$.

What I would like to know is:

A. Is there an answer already found for this question?

B. Is there any information off the top of your head which might assist me?

C. Is this problem incredibly hard?

Again, I apologize if this is not appropriate for this site. I am a sophomore undergraduate student, and I have been trying to answer or estimate this question for use as an upper bound for another larger question that I am working on.

Thanks for the help.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Get the first few values, then look 'em up at the Online Encyclopedia of Integer Sequences. $\endgroup$
    – Gerry Myerson
    Commented Jun 3, 2011 at 22:28
  • $\begingroup$ A. I doubt an exact number is known but I am pretty sure the question has been asked before and there is a lot of literature; B the rough order is $e^{n\log n}$ (give or take a constant factor in the exponent). C. That depends on the precision you want. The crude estimate I quoted is trivial but the more accurate bounds you want, the harder it gets. $\endgroup$
    – fedja
    Commented Jun 3, 2011 at 23:12
  • 2
    $\begingroup$ It is certainly not the state of the art but a quick literature search yields the asymptotics $\left[\frac 2e\frac n{\log^2 n}\gamma(n)\right]^n$ with $\gamma(n)=1+c(n)\frac{\log\log n}{\log n}$ and $c(n)$ eventually between $2$ and $4$. Is it good enough for your purposes? $\endgroup$
    – fedja
    Commented Jun 4, 2011 at 0:28
  • $\begingroup$ Thanks for your help. This will be enough to place an upper bound on what I was looking for, though I'm afraid I vastly underestimated the order of magnitude. Because of this, I doubt I'll be able to use this to produce a close estimate. For anyone interested in further pursuing this problem on it's own. If there is an estimate available for the average number of spanning trees in an n-vertex simple graph, I believe dividing the sum that I proposed: g(n) = The sum (t(i) * (a(i) choose (n - i - 1))) from i=x to y by a manipulation of this number may provide an estimate. $\endgroup$
    – malloc8
    Commented Jun 4, 2011 at 1:03
  • $\begingroup$ See mathoverflow.net/questions/68017/… $\endgroup$
    – Tony Huynh
    Commented Feb 11, 2020 at 14:28

1 Answer 1

Reset to default
4
$\begingroup$

Start here and you might find more.

http://oeis.org/A002905

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .