  Problems related to graph matching and isomorphisms are very important both
from a theoretical and practical perspective, with applications ranging from
image and video analysis to biological and biomedical problems. The graph
matching problem is challenging from a computational point of view, and
therefore different relaxations are commonly used. Although common relaxations
techniques tend to work well for matching perfectly isomorphic graphs, it is
not yet fully understood under which conditions the relaxed problem is
guaranteed to obtain the correct answer.
  In this paper we prove that the graph matching problem and its most common
convex relaxation, where the matching domain of permutation matrices is
substituted with its convex hull of doubly-stochastic matrices, are equivalent
for a certain class of graphs, such equivalence being based on spectral
properties of the corresponding adjacency matrices. We also derive results
about the automorphism group of a graph, and provide fundamental spectral
properties of the adjacency matrix.
