2
$\begingroup$

In this question we are counting labelled simple graphs. No concept of isomorphism is involved.

Let $G(n,e,t)$ be the number of labelled simple graphs with $n$ vertices, $e$ edges, and $t$ sets of three vertices which induce an odd number (1 or 3) of edges.

A block design enumeration problem can be solved if these numbers can be determined. However, I do not know any way to do that. I'm interested in any solution, like a summation, or generating function, or functional equation, or recurrence, or anything that allows computation of these numbers much faster than looking at all the graphs.

By considering the graph complement, we have $G(n,e,t) = G\left(n,\binom n2-e,\binom n3-t\right)$.

A generalisation would be to count labelled graphs with $n$ vertices, and $t_i$ sets of three vertices that induce $i$ edges for $i=0,1,2,3$, since the number of edges is easily determined from that information.

$\endgroup$
2
  • $\begingroup$ I do not completely understand the question: does n equal 3t? Or do you mean that I can label 3t out of the n vertices with colours from 1 to t, such that each colour occurs precisely 3 times and the subgraph induced by any of these colours contains either 1 or 3 edges? $\endgroup$ Jan 20, 2015 at 14:18
  • $\begingroup$ @Martin: There are $\binom n3$ sets of three vertices, each of which contains 0, 1, 2, or 3 edges. $t$ is the number of them that contain 1 or 3 edges. So $t$ is a number between $0$ and $\binom n3$. $\endgroup$ Jan 21, 2015 at 0:36

0

Your Answer

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