Graph Automorphisms from the Geometric Viewpoint

Abstract

An automorphism of a graph $G=(V,E)$ is a bijective map $\varphi$ from $V$ to itself such that $\varphi (v_i)\varphi (v_j)\in E$ $\iff$ $v_i{v}_j\in E$ for any two vertices $v_i$ and $v_j$. Denote by $\mathfrak{G}$ the group consisting of all automorphisms of $G$. Apparently, an automorphism of $G$ can be regarded as a permutation on $[n]=\{1,\dots ,n\}$, provided that $G$ has $n$ vertices. For each permutation $\sigma$ on $[n]$, there is a natural action on any given vector $\mathbf{u}=(u_1,\dots ,u_n{)}^t\in {\mathbb{C}}^n$ such that $\sigma \mathbf{u}=(u_{{\sigma }^{-1}1},u_{{\sigma }^{-1}2},\dots ,u_{{\sigma }^{-1}n}{)}^t$, so $\sigma$ can be viewed as a linear operator on ${\mathbb{C}}^n$. Accordingly, one can formulate a characterization to the automorphisms of $G$, {\it i.e.,} $\sigma$ is an automorphism of $G$ if and only if every eigenspace of $\mathbf{A}(G)$ is $\sigma$-invariant, where $\mathbf{A}(G)$ is the adjacency matrix of $G$. Consequently, every eigenspace of $\mathbf{A}(G)$ is $\mathfrak{G}$-invariant, which is equivalent to that for any eigenvector $\mathbf{v}$ of $\mathbf{A}(G)$ corresponding to the eigenvalue $\lambda$, $\mathrm{span}(\mathfrak{G}\mathbf{v})$ is a subspace of the eigenspace $V_{\lambda }$. By virtue of the linear representation of the automorphism group $\mathfrak{G}$, we characterize those extremal vectors $\mathbf{v}$ in an eigenspace of $\mathbf{A}(G)$ so that $\dim \mathrm{span}(\mathfrak{G}\mathbf{v})$ can attain extremal values, and furthermore, we determine the exact value of $\dim \mathrm{span}(\mathfrak{G}\mathbf{v})$ for any eigenvector $\mathbf{v}$ of $\mathbf{A}(G)$.

20 pages, 3 figures

Cited by in corpus (2)

• Symmetric and Spectral Realizations of Highly Symmetric Graphs
• Graph de Rham Cohomology and the Automorphsim Group