Geodesic
Study of graph isomorphism using Jordan forms of adjacency matrices
Prikladnaâ diskretnaâ matematika, no. 2 (2018), pp. 87-99

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: graph, directed graph, adjacency matrix, similarity matrices
Mots-clés : graph isomorphism, Jordan form of matrix. 
@article{PDM_2018_2_a6,
     author = {M. I. Volodicheva and S. N. Leora},
     title = {Study of graph isomorphism using {Jordan} forms of adjacency matrices},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {87--99},
     publisher = {mathdoc},
     number = {2},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2018_2_a6/}
}
TY  - JOUR
AU  - M. I. Volodicheva
AU  - S. N. Leora
TI  - Study of graph isomorphism using Jordan forms of adjacency matrices
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2018
SP  - 87
EP  - 99
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2018_2_a6/
LA  - ru
ID  - PDM_2018_2_a6
ER  - 
%0 Journal Article
%A M. I. Volodicheva
%A S. N. Leora
%T Study of graph isomorphism using Jordan forms of adjacency matrices
%J Prikladnaâ diskretnaâ matematika
%D 2018
%P 87-99
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2018_2_a6/
%G ru
%F PDM_2018_2_a6
M. I. Volodicheva; S. N. Leora. Study of graph isomorphism using Jordan forms of adjacency matrices. Prikladnaâ diskretnaâ matematika, no. 2 (2018), pp. 87-99. http://geodesic.mathdoc.fr/item/PDM_2018_2_a6/