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.

목차

Abstract
 1. Introduction
  1.1. The Automorphism Group of a Graph
  1.2. The Problems in the Automorphism Research
  1.3. The Contribution of the Article
 2. Terminology and Notation
 3. Basic Principle
 4. For Example Using Eigenvalue Partition
 5. Complexity Analysis
 6. Three Open Problems
 7. Conclusions
 Acknowledgements
 References

키워드

저자

• HAO Jian-Qiang [ State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, 100876, China, School of Computer Science and Information Engineering, Beijing Technology and Business University, 100048, China ]
• GONG Yun-Zhan [ State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, 100876, China ]
• LIU Hong-Zhi [ School of Computer Science and Information Engineering, Beijing Technology and Business University, 100048, China ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Hybrid Information Technology

• 간기

  격월간

• pISSN

  1738-9968

• 수록기간

  2008~2016

• 십진분류

  KDC 505 DDC 605