How to determine isomorphism in simple, connected (regular) graphs?

367 Views Asked by At

I am learning about regular graphs and have found that there are only 5 different options for a simple connected 3-regular graph with 8 vertices (source: http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html).

However, when I start plotting option for myself, I find it often very hard to determine whether two graphs are isomorphic or not. Here is an example with the first five graphs depicting the five options given in the link above and the sixth one of my additions: enter image description here

2

There are 2 best solutions below

0
On BEST ANSWER

The new option is equivalent to option 1. I found this by looking for cycles in the graph and checking in what way the cycles are attached to one another: you have four 3-cycles; two pairs of the four 3-cycles share an edge and then there are two edges (23 and 67 in Option 1) that connect everything.

0
On

I suspect your graph is isomorphic to option 1.

In these types of examples, I would first consider the cycle types of the graph. For instance, in your graph, we can easily see that we have $3$-cycles $(567), (568), (234), (134)$. And note that $(567)$ and $(234)$ has no adjacent vertices, as well as $(568)$ and $(134)$. Option 1 also has four $3$-cycles with the similar properties. So, we may want to suspect that they are isomorphic.

Finding an isomorphism though a little bit intuitional after suspecting. But in some "symmetric" cases it might be easier. For instance, I would consider a map from option 1 to your graph $$1 \to 3 ,\ 2 \to 1,\ 3 \to 7,\ 4 \to 6,\ 5 \to 5,\ 6 \to 8,\ 7 \to 2, \ 8 \to 4 $$