Graph Automorphisms from the Geometric Viewpoint

An automorphism of a graph G = (V,E) is a bijective map φ from V to itself such that φ(vi)φ(vj) ∈ E ⇔ vivj ∈ E for any two vertices vi and vj. Denote by G the group consisting of all automorphisms of G. Apparently, an automorphism of G can be regarded as a permutation on [n] = {1,..., n}, provided that G has n vertices. For each permutation σ on [n], there is a natural action on any given vector u = (u1,..., un) t ∈ Cn such that σu = (uσ−11, uσ−12,..., uσ−1n)t, so σ can be viewed as a linear operator on Cn. Accordingly, one can formulate a charac-terization to the automorphisms of G, i.e., σ is an automorphism of G if and only if every eigenspace of A(G) is σ-invariant, where A(G) is the adjacency matrix of G. Consequently, every eigenspace of A(G) is G-invariant, which is equivalent to that for any eigenvector v of A(G) corresponding to the eigenvalue λ, span(Gv) is a subspace of the eigenspace Vλ. By virtue of the linear representation of the automorphism group G, we characterize those extremal vectors v in an eigenspace of A(G) so that dim span(Gv) can attain extremal values, and furthermore, we determine the exact value of dim span(Gv) for any eigenvector v of A(G)