How to compute all undirectioned connected graphs that can be constructed from given V nodes and E edges

Question

I have 8 "types" of nodes, that can each appear once, twice or 3 times in one graph. Types 1,3 and 5 can appear 1 time, types 2 and 4 can appear two times and types 6, 7 and 8 can appear three times each. In total V=16 possible nodes.

Each node can have one, two or three connections points, depending on its type. In total 32 connection points possible.

How can I compute how many graphs I can build from these nodes and their connection points?

Also, one node cannot be connected to itself.

Answer 1

Computing numbers of non-isomorphic graphs with various parameters is not an easy task. Your best bet is to use a program like nauty to help you generate them. Sage is free and is equipped with a lot of nice graph theory tools, including nauty. Here is a Sage function that will print, sequentially, the number of graphs you are looking for on $0,1,\dots,M$ vertices:

def generate(M):
    for n in range(M+1):
        c = 0
        for G in graphs.nauty_geng(str(n) + " -d1 -D3"):
            D = G.degree_sequence()
            if D.count(1) <= 5 and D.count(2) <= 6 and D.count(3) <=5:
                 c = c+((factorial(5)*factorial(6)*factorial(5))/(factorial(5-D.count(1))*factorial(6-D.count(2))*factorial(5-D.count(3))*G.automorphism_group().order()))
        print n, c

Let me point out some parts of the code.

graphs.nauty_geng(str(n) + " -d1 -D3")

This generates all non-isomorphic graphs on $n$ vertices with minimum degree 1 and maximum degree 3.

if D.count(1) <= 5 and D.count(2) <= 6 and D.count(3) <=5:

This restricts to only graphs with at most 5 vertices of degree 1, at most 6 vertices of degree 2, and at most 5 vertices of degree 3.

 c = c+((factorial(5)*factorial(6)*factorial(5))/(5-factorial(D.count(1))*factorial(6-D.count(2))*factorial(5-D.count(3))*G.automorphism_group().order()))

The number of ways to assign labels 1,2,3,4,5 to the $n_1$ vertices of degree 1, labels 6,7,8,9,10,11 to the $n_2$ vertices of degree 2, and labels 12,13,14,15,16 to the $n_3$ vertices of degree 3 is: $\left(\frac{5!}{(5-n_1)!}\right)\left(\frac{6!}{(6-n_2)!}\right)\left(\frac{5!}{(5-n_3)!}\right)$. But since we may permute the vertices according to any automorphism of $G$ to obtain an equivalent labeling, we have an overcount of $|\mathrm{Aut}(G)|$, where $\mathrm{Aut}(G)$ is the automorphism group of $G$.

Now the output. The code runs fairly slowly past $M=10$. Here are some partial results:

0 0
1 0
2 10
3 80
4 940
5 9232
6 90470 
7 827620
8 6736970
9 49085240
10 316700810
11 1679283400
12 6905931400

I imagine it will take quite a bit more time to compute 13,14,15, and 16, so I've stopped it for now.