# Representation of the automorphism group of a graph is reducible

We can define a representation of the automorphism group $H$ of a $n$-vertex graph $\Gamma$ as the map $\rho : H \to M$ where $M$ is the set of all $n \times n$ binary matrices.

What is the implication from the perspective of the representation if the adjacency matrices of the graph and it's automorphisms are reducible i.e. the graph is not strongly connected?

Example: Permutation cycle graphs are not strongly connected.

Permutation Cycle Graph: A permutation cycle graph for a given permutation $\pi$ of a finite set $V$, is its cycle graph $\Gamma$ such that the vertex set is $V$ and the edges are pairs $\left(\mu, \omega\right)$ for which $\pi(\mu)=\omega$.

• What is $H$? Can you give an example for an easy graph? – draks ... Nov 26 '15 at 14:14
• You mention "strongly connected", which makes me wonder: are you implicitly assuming your graph is a directed graph? – Lee Mosher Nov 26 '15 at 14:53
• What do you mean by the map? Groups have more than one representation. – Tobias Kildetoft Nov 26 '15 at 19:12
• @draks..., I have added an easy example. – Omar Shehab Nov 26 '15 at 19:34
• You never said the representation was the adjacency matrix. You just said to take some representation. – Tobias Kildetoft Nov 27 '15 at 9:30