1
$\begingroup$

I would like to know if there is an explicit formula for the number of different (non isomorphic) simple graphs with a given number of vertices $p$ and edges $q$, and if yes what is it.

Trying to find it I've stumbled on an earlier question: Counting non isomorphic graphs with prescribed number of edges and vertices which was answered by Tony Huynh and in this answer an explicit formula is mentioned and said that it can be found here, but I can't find it there so I need help. Basically what I'm looking for is an explicit formula for $g_{p q}$ (of the form $g_{pq} = \; ...$ ) which is mentioned in the given link (and, for example, the book "Graphical Enumeration" by Harary and Palmer on page 82), or a way to obtain it.

The reason I need this is because I'm doing research on the statistical "physics" of (complex) networks and I want to see what I get when I define entropy using this... Thanks to all in advance :)

$\endgroup$
  • 5
    $\begingroup$ The formula is given at the link you’ve included. I’m sure there no essentially simpler formula. $\endgroup$ – Chris Godsil Dec 13 '17 at 2:20
  • $\begingroup$ Possible duplicate of Counting non-isomorphic graphs with prescribed number of edges and vertices $\endgroup$ – Neil Strickland Dec 13 '17 at 12:08
  • $\begingroup$ @ChrisGodsil - I can see there only the formula for the number of non-isomorphic graphs with $p$ vertices, labeled $g_p$. The best I can see from that link to get $g_{pq}$ is by finding and summing all coefficients of $x^q$ members in the explicit formula for $Z(S_p^{(2)})$. Is that what you mean? Because I really can't see a $g_{pq} =\, ... $ formula there, and that is what I meant by an "explicit formula". Is there no such thing? $\endgroup$ – Eugen Rožić Dec 13 '17 at 19:42
  • $\begingroup$ You won't find any simpler formula. At most there are rearrangements of the same thing. $\endgroup$ – Brendan McKay Dec 13 '17 at 22:46
  • $\begingroup$ As Chris says, there is no formula that does not involve extracting the relevant coefficients from this sum over cycle types of permutations. The good news is that this can easily be done for specific smallish values of $p$ and $q$. $\endgroup$ – Gordon Royle Dec 13 '17 at 22:46
1
$\begingroup$

Seems like there is no better solution than summing the coefficients of all the $x^q$ members from the explicit formula for $Z\left(S_p^{(2)}\right)$, as people said in the comments to my question. Thank you all for your help.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.