The Determination of Graph Isomorphism Using R Software
DOI:
https://doi.org/10.53555/nnms.v7i11.945Keywords:
adjacency matrix, permutation matrix, graph sequence, k-regular graph, eigenvalue, isomorphism mappingAbstract
This paper considers the determination of graph isomorphism using R. After the preliminaries about graph theory is introduced systematically, the graph isomorphism determination process are studied. Then computer program for the determination of graph isomorphism is written using R. According to these R codes, the paper determines the isomorphism of three 3-regular graphs on 6 vertices and three 3-regular graphs on 8 vertices respectively, and the output proves that the R codes are very practical and effective.
References
R. Dondi, G. Mauri, I. Zoppis, Graph isomorphism, Encyclopedia of Bioinformatics & Computational Biology 1 (2019) 933{939.
R. C. Read, D. G. Corneil, The graph isomorphism disease, Journal of Graph Theory 1 (4) (2010) 339{363.
R. Mathon, A note on the graph isomorphism counting problem, Information Processing Letters 8 (3) (1979) 131{136.
H. L. Bodlaender, Bodlaender, h.: Polynomial algorithm for graph isomorphism and chromatic index on partial k-trees. journal of algorithms 11(4), 631-643, Journal of Algorithms 11 (4) (1990) 631{643.
V. Arvind, P. P. Kurur, Graph isomorphism is in spp, Information & Computation 204 (5) (2013) 835{852.
M. Pelillo, Replicator equations, maximal cliques, and graph isomorphism, Neural Computation 11 (8) (1999) 1933.
S. D. Berry, J. B. Wang, Two-particle quantum walks: Entanglement and graph isomorphism testing, Physical Review A 83 (4) (2011) 786{792.
C. Moore, A. Russell, P. ?niady, On the impossibility of a quantum sieve algorithm for graph isomorphism, Siam Journal on Computing 39 (6) (2010) 2377{2396.
Lubiw, Anna, Some np-complete problems similar to graph isomorphism, Siam Journal on Computing 10 (1) (2006) 11{21.
Y. Aflalo, A. Bronstein, R. Kimmel, On convex relaxation of graph isomorphism, Proceedings of the National Academy of Sciences of the United States of America 112 (10) (2015) 2942{7.
Published
Issue
Section
License
Copyright (c) 2020 Journal of Advance Research in Mathematics And Statistics (ISSN: 2208-2409)
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
You are free to:
- Share — copy and redistribute the material in any medium or format for any purpose, even commercially.
- Adapt — remix, transform, and build upon the material for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
Under the following terms:
- Attribution — You must give appropriate credit , provide a link to the license, and indicate if changes were made . You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
Notices:
You do not have to comply with the license for elements of the material in the public domain or where your use is permitted by an applicable exception or limitation .
No warranties are given. The license may not give you all of the permissions necessary for your intended use. For example, other rights such as publicity, privacy, or moral rights may limit how you use the material.
