1
$\begingroup$

Does Automorphism group combined with the order and degree uniquely determine any regular graph? What about any (non-regular) graph?

I think yes, because the automorphism contain within them the adjacency relations, which, I think could be decoded given the order and degree of the graph. Are there any two graphs that have the same automorphism group, order and degree but are not isomorphic? Thanks beforehand.

$\endgroup$
3
$\begingroup$

Non-regular? No. The two following graphs both have the same list of degrees ($3,2\cdot 5, 1\cdot 3$) and the same automorphism group (the trivial group):
$G_1$: Edges A-B, A-C-D, A-E-F-G-H-I.
$G_2$: Edges A-B, A-C-D-E, A-F-G-H-I.
In each case, an automorphism must fix the lone vertex of order 3, and send each chain heading away from that vertex to a chain of the same length. Within each groups, the chains have different lengths and must therefore each be fixed. Between the two groups, the list of chain lengths is different.

Regular? No. The two following groups have the same number of vertices ($19$), the same common degree ($4$), and the same automorphism group (dihedral):

$G_3$: The vertices are the integers mod $19$. There is an edge between $m$ and $n$ if and only if $m-n\in \{-2,-1,1,2\}$ mod $19$. The triangles including $0$ are $\{0,1,2\}$, $\{-1,0,1\}$, and $\{-2,-1,0\}$, so edges $(k,k+1)$ are the only ones in two triangles each and can be distinguished from edges $(k,k+2)$.

$G_4$: The vertices are the integers mod $19$. There is an edge between $m$ and $n$ if and only if $m-n\in \{-3,-1,1,3\}$ mod $19$. The quadrilaterals including $0$ are $(0,1,2,3)$, $(0,1,4,3)$, $(0,3,2,-1)$, $(0,1,2,-1)$, $(0,1,-2,-3)$, $(0,1,-2,-1)$, $(0,-1,-2,-3)$, and $(0,-1,-4,-3)$. Edges $(k,k+1)$ are in five quadrilaterals each, while edges $(k,k+3)$ are in three quadrilaterals each, so we can distinguish between them.

In each case, we can distinguish between edges of the type $(k,k+1)$ and the other type present. Each automorphism group must therefore be contained in the automorphism group of the subgraph of just those edges - which is the dihedral group $D_{19}$. A quick check verifies that everything in that dihedral group is in fact an automorphism of each of these groups, and we're done.

$\endgroup$
  • $\begingroup$ Thanks! The last two graphs were circulant graphs, right? So, is there any extra criterion required to uniquely determine the graph along the three parameters I mentioned? $\endgroup$ – vidyarthi Mar 12 at 10:10
  • $\begingroup$ Probably nothing practical. I just invented these examples off the top of my head. Oh, and there's nothing special about 19 there, other than being big enough. Anything greater than 12 definitely works. $\endgroup$ – jmerry Mar 12 at 10:14
  • $\begingroup$ But those two last graphs are circulant graphs. Anyways, so is there no criterion except perfect isomorphism to completely determine a graph, I mean is there no extra parameter except isomorphism that can be added to the parameters I gave to make it equivalent to isomorphism? $\endgroup$ – vidyarthi Mar 12 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.