8
$\begingroup$

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?

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?

Are these generating function methods actually useful for computing these numbers when the graphs are 'large'? Thanks!

Update: Here is the list:

http://www.win.tue.nl/~aeb/graphs/cospectral/triangles.html

I haven't seen it in the OEIS, though.

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?

$\endgroup$
2
  • $\begingroup$ Possible? Yes. Quick? I doubt it. Having such information might be too useful in solving certain NP hard problems like Max-Clique. There may be literature on #P (P-sharp?) complexity which tells you how good an approximation you need to win a Clay Prize. Gerhard "Would Accept A Clay Prize" Paseman, 2011.05.12 $\endgroup$ May 12, 2011 at 17:58
  • 2
    $\begingroup$ Judging from sequences A006785 and A024607 in OEIS, even enumerating labelled or unlabelled triangle-free graphs with $n$ vertices is difficult. $\endgroup$ May 13, 2011 at 0:41

1 Answer 1

7
$\begingroup$

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

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.

So counting $K_4$'s as well seems even more hopeless.

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.

And why have these enumeration problems not been solved? Perhaps they are too hard, or we're too stupid. (Me, at least.)

$\endgroup$
0

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.