Fdtxjr

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.

Non-regular? No. The two following graphs both have the same list of degrees ($3,2cdot 5, 1cdot 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-nin -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-nin -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.