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 :)

Improve this question
$\endgroup$
5
  • 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, 2017 at 2:20
  • $\begingroup$ Possible duplicate of Counting non-isomorphic graphs with prescribed number of edges and vertices $\endgroup$
    – Neil Strickland
    Dec 13, 2017 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, 2017 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, 2017 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, 2017 at 22:46

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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