Number of graphs with a given number of nodes, edges and triangles - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T11:08:44Z http://mathoverflow.net/feeds/question/64810 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/64810/number-of-graphs-with-a-given-number-of-nodes-edges-and-triangles Number of graphs with a given number of nodes, edges and triangles Camilo Sarmiento 2011-05-12T16:35:30Z 2011-06-14T14:38:25Z <p>Hi. Does anyone know if it is possible to enumerate the set of labeled/unlabeled graphs (loopless, undirected, only one edge between pairs of nodes) having a given number of nodes, edges and triangles? what about including more information, like number of tetrahedra, etc.? If not, why? </p> <p>The solution to the unlabeled case with given number of nodes and edges, and to many other enumeration problems can be given in terms of Polya's theorem (by Harary, de Bruijn, Robinson, Read, Polya, etc.). Is it possible to give the resulting generating functions an interpretation in terms of order theory and use this to study their algebraic properties?</p> <p>Are these generating function methods actually useful for computing these numbers when the graphs are 'large'? Thanks!</p> <p>Update: Here is the list:</p> <p><a href="http://www.win.tue.nl/~aeb/graphs/cospectral/triangles.html" rel="nofollow">http://www.win.tue.nl/~aeb/graphs/cospectral/triangles.html</a></p> <p>I haven't seen it in the OEIS, though.</p> <p>Does it get any easy if we wanted to enumerate, instead, the set of graphs on given number of vertices and trangles -irrespective- of the number of edges?</p> http://mathoverflow.net/questions/64810/number-of-graphs-with-a-given-number-of-nodes-edges-and-triangles/64858#64858 Answer by Chris Godsil for Number of graphs with a given number of nodes, edges and triangles Chris Godsil 2011-05-13T01:06:06Z 2011-05-13T01:06:06Z <p>Polya theory provides us with an algorithm that allows us to compute the number of isomorphism classes of graphs with \$n\$ vertices and \$m\$ edges, for given \$n\$ and \$m\$. It does not provide a formula in terms of \$n\$ and \$m\$ and it does not even provide a generating function. (Well, we can express it in terms of so-called cycle index, but that is just giving a name to the unknown.) </p> <p>If now we ask for the number of graphs in terms of \$n\$, \$m\$ and the number of triangles then we are lost. I have never seen an enumeration of triangle-free graphs, let alone triangle-free graphs with a given number of edges. And if we cannot count the graphs in a given class, counting isomorphism classes of graphs in the class is usually beyond us as well.</p> <p>So counting \$K_4\$'s as well seems even more hopeless.</p> <p>In the cases where Polya's method works, it can provide asymptotic information for large \$n\$, but not formulas. So for large \$n\$ we know that the number of isomorphism classes of graphs on \$n\$ vertices is asymptotic to \$2^n/n!\$, but there is no exact formula.</p> <p>And why have these enumeration problems not been solved? Perhaps they are too hard, or we're too stupid. (Me, at least.)</p>