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$.

enter image description here

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

Your Answer

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

Browse other questions tagged or ask your own question.