Study of graph isomorphism using Jordan forms of adjacency matrices

M. I. Volodicheva ; S. N. Leora

Prikladnaâ diskretnaâ matematika, no. 2 (2018), pp. 87-99.

Résumé

It is proposed to use a Jordan form of adjacency matrices to establish the absence of isomorphism between direct graphs. The problem of reduction of a matrix to a Jordan form has polynomial time complexity. The upper estimate of the required number of operations for $n$-vertex graph is $\mathrm O(n^4)$. It is shown that the Jordan form of the adjacency matrix contains more information about the structure of the graph than its spectrum determinated by the eigenvalues of the adjacency matrix and their multiplicity. As a result of research on specific examples it was found that the isospectral matrices of the same set of eigenvalues may have different Jordan forms. This means that the adjacency matrices are not similar and therefore are not permutation similar, indicating a lack of isomorphism between direct graphs.

Détail

Keywords: graph, directed graph, adjacency matrix, similarity matrices
Mots-clés : graph isomorphism, Jordan form of matrix.

Bibliographie

[1] Tsvetkovich D., Dub M., Zakhs H., Spectra of graphs. Theory and application, Naukova Dumka, Kiev, 1984, 378 pp. (in Russian) | MR

[2] Kas'yanov V. N., Yevstigneyev V. A., Graphs in programming: processing, visualization and application, BKHV-Peterburg, SPb., 2003, 1104 pp. (in Russian)

[3] Il'yashenko M. B., Goldobin A. A., “The solution of problem of search of graph isomorphism for designing special computers”, Radioelektronika, Informatika, Upravleniye, 2012, no. 1, 31–36 (in Russian)

[4] Marley V. Ye., Plotnikov S. N., “The algorithm for recognizing isomorphic investment of algorithmic networks”, Vestnik VGU IT, 2014, no. 3, 72–75 (in Russian)

[5] Newman M. E. J., Networks: an Introduction, Oxford University Press, Oxford, 2010, 784 pp. | MR | Zbl

[6] Sandryhaila A., Moura J. M. F., “Discrete signal processing on graphs”, IEEE Trans. Signal Process., 61:7 (2013), 1644–1656 | DOI | MR

[7] Sandryhaila A., Moura J. M. F., “Discrete signal processing on graphs: frequency analysis”, IEEE Trans. Signal Process., 62:12 (2014), 3042–3054 | DOI | MR

[8] Teke O., Vaidyanathan P. P., “Uncertainty principles and sparse eigenvectors of graphs”, IEEE Trans. Signal Process., 65:20 (2017), 5406–5420 | DOI | MR

[9] Babai L., Graph isomorphism in quasipolynomial time, v1:11 Dec 2015, v2:19 January 2016, arXiv: 1512.03547 | MR

[10] Zykov A. A., Fundamentals of Graph Theory, Vuzovskaya kniga, Moscow, 2004, 664 pp. (in Russian) | MR

[11] Khitrov G. M., “On the graph diversity and the application of this concept to the problem of graph isomorphism”, Vestn. S.-Peterb. un-ta. Ser. 10, 2006, no. 2, 91–100 (in Russian)

[12] Pogozhev S. V., Khitrov G. M., “On the problem of graph isomorphism and one matrix algorithm to solve it”, Vestn. S.-Peterb. un-ta.Ser. 10, 2006, no. 1, 1–5 (in Russian)

[13] Pogrebnoy A. V., “Complete invariant of the graph and the algorithm of its calculation”, Izvestiya Tomskogo Politekhnicheskogo Universiteta, 325:5 (2014), 110–122 (in Russian)

[14] Pogrebnoy A. V., “Method for determining the similarity of structures of graphs based on the allocation of partial isomorphism in geoinformatics tasks”, Izvestiya Tomskogo Politekhnicheskogo Universiteta, 326:11 (2015), 56–66 (in Russian)

[15] Pogrebnoy V. K., Pogrebnoy A. V., “A polynomial algorithm for computing the complete invariant of the graph based on the integral handle structure”, Izvestiya Tomskogo Politekhnicheskogo Universiteta, 323:5 (2013), 152–159 (in Russian)

[16] McKay B. D., “Practical graph isomorphism”, Congressus Numerantium, 30 (1981), 45–87 | MR | Zbl

[17] McKay B. D., Piperno A., “Practical graph isomorphism, II”, J. Symbolic Computation, 60 (2014), 94–112 | DOI | MR | Zbl

[18] Darga P. T., Sakallah K. A., Markov I. L., “Faster symmetry discovery using sparsity of symmetries”, Proc. 45th Design Automation Conf., 2004, 149–154

[19] Junttila T., Kaski P., “Engineering an efficient canonical labeling tool for large and sparse graphs”, Proc. 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics, SIAM, 2007, 135–149

[20] López-Presa J. L., Fernández A. A., “Fast algorithm for graph isomorphism testing”, Proc. 8th Intern. Symp. Experimental Algorithms, 2009, 221–232

[21] Khorn R., Dzhonson Ch., Matrix Analysis, Mir Publ., Moscow, 1989, 655 pp. (in Russian) | MR

[22] Faddeyev D. K., Faddeyeva V. N., Computational Methods of Linear Algebra, Lan' Publ., SPb., 2009, 736 pp. (in Russian) | MR

[23] Uilkinson Dzh. H., The Algebraic Problem of Eigenvalues, Nauka Publ., Moscow, 1970, 564 pp. (in Russian)

[24] Cardon D. A., Tuckfield B., “The Jordan canonical form for a class of zero–one matrices”, Linear Algebra and its Appl., 435:11 (2011), 2942–2954 | DOI | MR | Zbl

[25] Nina H., Soto R. L., Cardoso D. M., “The Jordan canonical form for a class of weighted directed graphs”, Linear Algebra and its Appl., 438:1 (2013), 261–268 | DOI | MR | Zbl

[26] Beklemishev D. V., Additional Chapters of Linear Algebra, Nauka Publ., Moscow, 1983, 336 pp. (in Russian) | MR

[27] Volodicheva M. I., Grigor'yev-Golubev V. V., Leora S. N., Eigenvectors, Jordan Forms and Matrix Functions. MatLab, Mathematica, Maple, SPbGMTU Publ., SPb., 2009, 175 pp. (in Russian)

[28] Prolubnikov A. V., “Direct algorithm of graph isomorphism testing”, Komp'yuternaya Optika, 31:3 (2007), 86–92 (in Russian)

[29] Deri J. A., Moura J. M. F., Graph Equivalence Classes for Spectral Projector-Based Graph Fourier Transforms, 11 Jan 2017, arXiv: 1701.02864v1[cs.SI]

[30] Deri J. A., Moura J. M. F., “Spectral projector-based graph Fourier transforms”, IEEE J. Selected Topics in Signal Processing, 11:6 (2017), 785–795 | DOI