Sorry I'm new here, can someone please help me out with this question. I missed a couple of lectures and I don't even know where to start. I'm trying to find all the non-isomorphic graphs whose degree sequence is $(6,3,3,3,3,3,3)$
[Math] Find all the non-isomorphic graphs whose degree sequence is $(6,3,3,3,3,3,3)$
graph theory
Related Solutions
One way you can approach this problem is noting that the vertices with degree 2 can be "reduced" to an edge without changing degrees. So we want to find all non-isomorphic connected simple graphs with degrees (3,3,3,3,4,4) first. Consider the complement of this graph; you get (1,1,2,2,2,2) as the degrees. There are only a few ways in which this can happen: you can have a lone edge and a 4-cycle, a 3-path and a 3-cycle, or a 6-path. (I believe these are the only cases)
Next, convert these back into graphs and the question is reduced to finding edges (which could be the same edge, giving a 3-long "edge") to "lengthen" by inserting a vertex in the middle.
It looks like there's not going to be a clever way to do this. Using geng 14 13:13 -c (the package geng comes with Nauty), we can generate representatives from each isomorphism class of 14-vertex trees. I wrote a GAP script to identify the ones with the degree sequence [ 5, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1 ]. It turns out there's 150 of them, drawn below (with the vertices ascribed their degrees):
Related Question
- [Math] Count the number of non-isomorphic graphs for the given degree sequence
- [Math] Find all non-isomorphic complete bipartite graphs with at most 7 vertices
- [Math] I need an example of two non-isomorphic graphs with the same degree sequence.
- The smallest $n$ for which loopless graphs contain non-isomorphic $n$-vertex graphs with the same degree sequence
Best Answer
Hint: Imagine a central vertex with degree 6 connected to the other six vertices (say, arranged on a circle). To get the vertices on the circle to have degree 3, each one must be connected to two others on the circle. If we label the vertices on the circle $v_1$ to $v_6$, then, without loss of generality, $v_1 \sim v_2$ and $v_2 \sim v_3$. After that, you have some freedom in adding edges.
Try it! See how many nonisomorphic ways you can find to fill in the missing edges.