3
$\begingroup$

I have 5 nodes with the degree 2, 2, 2, 3, 5. How do I find all non-isomorphic graphs I can make out of these 5 nodes? All the nodes must be connected with eachother.

One way I think would work would be to bruteforce it by writing a chart for every possibility.

Like if A represents 2, B - 3 and C - 5 and where an X represents an edge.

  A A A B C A   X X A X     X A X       X B   X   X C     X   2X 

But that seems like it would be hard to not miss/add a graph and takes some time to do. Does any one know a way to do this?

Updates:

  • Loops are allowed
  • Multiple edges between same two nodes are allowed
  • 0
    @user13901: Ah, my mistake :-)2011-07-30

1 Answers 1

3

The valence 2 nodes can be thought of as adding an internal vertex to an existing edge. So we begin by looking at the number of graphs that have two vertices of valence 3 and 5. There are two of these. The first graph is a theta graph with an extra loop at one end. The second is a loop connected to two loops by an edge. Now we need to study the number of distinct ways to add 3 bivalent vertices to each graph.

For the first graph type there are two ways to add all three to the same edge, 3 ways to add them to different edges, and 2 ways to add them to 3 different edges. So that's 7 of the first type.

For the second graph type there are three ways to add them to the same edge, 7 ways to add them to two edges and 3 ways to add them to three edges. So that's 13 of the second kind of graph. So I get 20 total.

In summary, by looking at the graph with bivalent vertices removed, the analysis is simplified a bit, although it is still brute force.

  • 0
    This way of solution will only work good on smaller graphs like this one. But I can't seem to find a better way of doing it. Thank you!2011-07-30