A Note on Eigenvalues and Asymmetric Graphs

This note is intended as a contribution to the study of quantitative measures of graphcomplexity that use entropy measures based on symmetry. Determining orbit sizes of graph automorphismgroups is a key part of such studies. Here we focus on an extreme case where every orbitcontains just a single vertex. A permutation of the vertices of a graph G is an automorphism if, andonly if, the corresponding permutation matrix commutes with the adjacency matrix of G. This factestablishes a direct connection between the adjacency matrix and the automorphism group. In particular,it is known that if the eigenvalues of the adjacency matrix of G are all distinct, every non-trivialautomorphism has order 2. In this note, we add a condition to the case of distinct eigenvalues thatmakes the graph asymmetric, i.e., reduces the automorphism group to the identity alone. In addition,we prove analogous results for the Google and Laplacian matrices. The condition is used to buildan O(n(3)) algorithm for detecting identity graphs, and examples are given to demonstrate that it issufficient, but not necessary.