I am a very beginner at graph/group transitivity. Given a graph $G$ or its adjacency matrix $A_G$, what strategies do I have to show if it is transitive? I know $G$ is vertex-transitive if the automorphism group of $G$ is transitive, but I just don't understand them.
Specifically, I got the following questions:
Q$1$: If there exists a permutation matrix $P=\begin{bmatrix}0&1&\dots&\dots&0\\
0&0&1&\dots&0\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
0&0&0&0&1\\
1&0&0&0&0\end{bmatrix}$ such that $PA_GP^{-1}=A_G$, then $G$ is vertex-transitive. Is it true or false?
Q$2$: If $G$ is vertex-transitive, then there exists a permutation matrix $P=\begin{bmatrix}0&1&\dots&\dots&0\\
0&0&1&\dots&0\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
0&0&0&0&1\\
1&0&0&0&0\end{bmatrix}$ such that $PA_GP^{-1}=A_G$. Is it true or false?
I'm not sure whether the above two are true or not, but I think it may be a more explicit way to understand vertex transitivity. I would appreciate it so much if you would mention anything regarding how to understand graph vertex transitivity. Thank you!
Best Answer
This statement is true. This is essentially saying the graph has rotational symmetry. That is, if you rotate the graph by moving vertex $1$ to vertex $2$, and so on until you get to vertex $n$ which you move back to $1$ you'll end up with the same graph. Clearly you can keep rotating to move one vertex to any other vertex.
This statement is false. This requires that the graph be rotationally symmetric. Not only that, you a declaring that a very specific rotation works. The one way where you send vertex $1$ to $2$ and so on. The problem here is even if the graph is rotationally symmetric, if you reorder the vertices the permutation specified by that $P$ may not work. For example imagine a square with vertices reading clockwise 1,3,2,4. The permutation 1->2->3->4->1 no longer preserves the edges of the graph. You'd need to do 1->3->2->4->1 which corresponds to a different matrix. (same as $P$ with the middle two columns swapped).