The Determination of Graph Isomorphism Using R Software

Authors

  • Chaobing He School of Mathematics and Statistics, Anyang Normal University, Anyang 455000, China

DOI:

https://doi.org/10.53555/nnms.v7i11.945

Keywords:

adjacency matrix, permutation matrix, graph sequence, k-regular graph, eigenvalue, isomorphism mapping

Abstract

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

2020-11-30

How to Cite

He, C. . (2020). The Determination of Graph Isomorphism Using R Software. Journal of Advance Research in Mathematics and Statistics (ISSN 2208-2409), 7(11), 01-06. https://doi.org/10.53555/nnms.v7i11.945

Similar Articles

You may also start an advanced similarity search for this article.