I'd love your help with this question.
Let $n\geq3$ be a fixed integer. How many non-isomorphic graphs with $p$ vertices and $q$ edges are there where $p+q=n$?
Thank you very much.
Crossposted at MSE.
$\begingroup$
$\endgroup$
3
-
4$\begingroup$ I changed the tags. On a different note, this question could do with some attention from the points at mathoverflow.net/howtoask - for example, what is your motivation? How did this question come up? $\endgroup$– David Roberts ♦Commented Jun 17, 2011 at 0:41
-
5$\begingroup$ This duplicates a question at math.stackexchange. math.stackexchange.com/questions/45815/counting-graphs $\endgroup$– Jim ConantCommented Jun 17, 2011 at 1:30
-
6$\begingroup$ Blaise - the usual practice is to not ask in both MO and math.SE at the same time. Usually (as in, almost always) a question will only be suitable for one of them, it may be that the asker misjudges the 'audience', and so needs to swap to the other. $\endgroup$– David Roberts ♦Commented Jun 17, 2011 at 1:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Using the Combinatorica package in Mathematica, the command NumberOfGraphs$[p,q]$ returns the number of non-isomorphic graphs with $p$ vertices and $q$ edges. If you want to implement this yourself, you may want to proceed here first.
There is an explicit (but rather complicated) formula which you can find here. The formula is obtained via Pólya's Enumeration Theorem.
Edit: Indeed it is a standard application of Pólya theory to obtain formulas for the number of nonisomorphic graphs with $p$ vertices and $q$ edges. (Counting the number where the total number of vertices and edges is $n$ can be obtained from this.) The standard book on graph enumeration is "Graphical enumeration" by Harary and Palmer. There is a web site with many sequences arising from results discussed in the book.
answered Jun 17, 2011 at 3:22
-
7$\begingroup$ Wow! Never in a million years would I have guessed there was an explicit formula, and what a formula it is! $\endgroup$ Commented Jun 17, 2011 at 3:46