An Example for a Graph with the Quaternion Group as Automorphism Group

Question

I am reading "Graphs of Degree Three with given Abstract Group" (by Robert Frucht) where the author describes (somewhat tedious) algorithms to construct suitable graphs starting from a given group. I would like to see a graph associated with the quaternion group as its automorphism group. Following the given algorithm the graph should have 32 vertices (or even less?). Has anyone, by chance, an available solution? If not, then I will find it myself. Thank you!

Answer 1

I have read the same paper in 2014 and constructed the graph in the picture on $32$ vertices. The group $Q_8 = (\{\pm 1, \pm i, \pm j, \pm k\},\cdot)$ is its automorphism group which is in detail $+1 \backsimeq \iota$,

$-1 \backsimeq (1,3)\circ(2,4)\circ(5,7)\circ(6,8)\circ(9,11)\circ(10,12)\circ(13,15)\circ(14,16)\circ(17,19)\circ(18,20)\circ(21,23)\circ(22,24)\circ(25,27)\circ(26,28)\circ(29,31)\circ(30,32)$,

$+i \backsimeq (1,2,3,4)\circ(5,6,7,8)\circ(9,10,11,12)\circ(13,14,15,16)\circ(17,18,19,20)\circ(21,22,23,24)\circ(25,26,27,28)\circ(29,30,31,32)$,

$-i \backsimeq (1,4,3,2)\circ(5,8,7,6)\circ(9,12,11,10)\circ(13,16,15,14)\circ(17,20,19,18)\circ(21,24,23,22)\circ(25,28,27,26)\circ(29,32,31,30)$,

$+j \backsimeq (1,6,3,8)\circ(2,5,4,7)\circ(9,13,11,15)\circ(10,16,12,14)\circ(17,32,19,30)\circ(18,31,20,29)\circ(21,28,23,26)\circ(22,27,24,25)$,

$-j \backsimeq (1,8,3,6)\circ(2,7,4,5)\circ(9,15,11,13)\circ(10,14,12,16)\circ(17,30,19,32)\circ(18,29,20,31)\circ(21,26,23,28)\circ(22,25,24,27)$,

$+k \backsimeq (1,7,3,5)\circ(2,6,4,8)\circ(9,14,11,16)\circ(10,13,12,15)\circ(17,29,19,31)\circ(18,32,20,30)\circ(21,25,23,27)\circ(22,28,24,26)$,

$-k \backsimeq (1,5,3,7)\circ(2,8,4,6)\circ(9,16,11,14)\circ(10,15,12,13)\circ(17,31,19,29)\circ(18,30,20,32)\circ(21,27,23,25)\circ(22,26,24,28)$

I did not try and find a graph on less vertices. Can you take it from here?