An algorithm for natural indexing of auto-morphic equivalence classes of vertices and edges in finite graphs is proposed. Using this indexing, the alternative description of graph isomorphism classes is constructed. It is also demonstrated that one can apply such classical concepts as colouring, operations on graphs and subgraphs to the graph isomorphism classes.
Download file
Counter downloads: 76
- Title Alternative approaches to the description of classes of isomorphic graphs
- Headline Alternative approaches to the description of classes of isomorphic graphs
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3 (25)
- Date:
- DOI
Keywords
инварианты графов, классы симметрии рёбер, классы симметрии вершин, изоморфизм графовAuthors
References
Харари Ф. Теория графов. М.: КомКнига, 2006. 296 с.
Kobler J., Schoning U., and Toran J. The Graph Isomorphism Problem: its Structural Complexity. Berlin: Birkhauser, 1993. 160 p.
Harary F. A survey of the reconstruction conjecture // Graphs and Combinatorics. Lecture Notes in Mathematics. 1974. V. 406. P. 18-28.
Weininger D., Weininger A., and Weininger J. SMILES. 2. Algorithm for generation of unique SMILES notation // J. Chem. Inf. Comput. Sci. 1989. V.29. No. 2, P. 97-101.
Katebi H., Sakallah K., and Markov I. L. Graph symmetry detection and canonical labelling: differences and synergies // Proc. Turing-100, EPIC 2012. V. 10. P. 181-195.
Sparrow M. K. A linear algorithm for computing automorphic equivalence classes: the numerical signatures approach // Social Networks. 1993. V. 15. P. 151-170.
Southwell R. Finding Symmetries in Graphs. Ph.D. thesis. University of York, UK, 2006. 109 p.
Кинг Р. Химические приложения топологии и теории графов. М.: Мир, 1987. 560 с.
Фларри Р. Группы симметрии. Теория и химические приложения. М.: Мир, 1983. 400 с.
Bonchev D. and Rouvray D. H. Chemical Graph Theory: Introduction and Fundamentals. N.Y.: Gordon and Breach science publishers, 1991. 300 p.
Darga P., Sakallah K., and Markov I. L. Faster symmetry discovery using sparsity of symmetries // Proc. 45st Design Automation Conference. N.Y.: ACM, 2008. P. 149-154.
Aloul F. A., Ramani A., Markov I. L., and Sakallah K. A. Solving difficult instances of Boolean satisfiability in the presence of symmetry // IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems. 2003. V.22. No. 9, P. 1117-1137.
Holmes M. R. Elementary Set Theory with a Universal Set. Louvain-la-Neuve: Academia, 1998. 241 p.
Зыков А. А. Основы теории графов. М.: Наука, 1987. 383с.
Diestel R. Graph Theory. 3rd edition. Heidelberg: Springer Verlag, 2005. 451 p.
Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. М.: Высшая школа, 1976. 391 с.
Alternative approaches to the description of classes of isomorphic graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 3 (25).
Download full-text version
Counter downloads: 173