earticle

영어

To solve the automorphism group of a graph is a fundamental problem in graph theory. Moreover, it usually is an essential process for graph isomorphism testing. At present, because existing algorithms ordinarily cannot efficiently compute the automorphism group of a graph, ones cannot entirely resolve the graph isomorphism problem. To calculate the automorphism group of a weighted graph, first, briefly review the history of automorphism. Second, introduce the concept of eigenvalue partition. Third, using algebraic methods, examine not only the relationships between the diagonal form of an adjacency matrix and its eigenvalues and eigenvectors, but also the relationships between its eigenvalues and eigenvectors and the automorphism group. Furthermore, prove Theorem 2 to 8. In addition, propose Conjecture 1 and three open problems. By these theorems, present a novel method to resolve the automorphism group of a weighted graph. If a graph has no duplicate eigenvalues and Conjecture 1 is true, it can determine the automorphism group of a weighted graph in polynomial time by the method. Although this method has certain limitations and needs improvements, it is theoretically a necessary complement to solve the automorphism group. Finally, it shows the close relationships that exist between an orthogonal matrix and a permutation matrix, also an orthogonal matrix and an automorphism.