Standard

Study of graph isomorphism using Jordan forms of adjacency matrices. / Volodicheva, M. I.; Leora, S. N.

In: Prikladnaya Diskretnaya Matematika, No. 40, 01.06.2018, p. 87-99.

Research output: Contribution to journal › Article › peer-review

Harvard

Volodicheva, MI & Leora, SN 2018, 'Study of graph isomorphism using Jordan forms of adjacency matrices', Prikladnaya Diskretnaya Matematika, no. 40, pp. 87-99. https://doi.org/10.17223/20710410/40/7

APA

Volodicheva, M. I., & Leora, S. N. (2018). Study of graph isomorphism using Jordan forms of adjacency matrices. Prikladnaya Diskretnaya Matematika, (40), 87-99. https://doi.org/10.17223/20710410/40/7

Vancouver

Volodicheva MI, Leora SN. Study of graph isomorphism using Jordan forms of adjacency matrices. Prikladnaya Diskretnaya Matematika. 2018 Jun 1;(40):87-99. https://doi.org/10.17223/20710410/40/7

Author

Volodicheva, M. I. ; Leora, S. N. / Study of graph isomorphism using Jordan forms of adjacency matrices. In: Prikladnaya Diskretnaya Matematika. 2018 ; No. 40. pp. 87-99.

BibTeX

@article{e3e305148ca748119ca4af79a1dbc180,
title = "Study of graph isomorphism using Jordan forms of adjacency matrices",
abstract = "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 O(n4). 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 isospec- tral 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 = "Adjacency matrix, Directed graph, Graph, Graph isomorphism, Jordan form of matrix, Similarity matrices",
author = "Volodicheva, {M. I.} and Leora, {S. N.}",
year = "2018",
month = jun,
day = "1",
doi = "10.17223/20710410/40/7",
language = "English",
pages = "87--99",
journal = "Prikladnaya Diskretnaya Matematika",
issn = "2071-0410",
publisher = "Tomsk State University",
number = "40",

}

RIS

TY - JOUR

T1 - Study of graph isomorphism using Jordan forms of adjacency matrices

AU - Volodicheva, M. I.

AU - Leora, S. N.

PY - 2018/6/1

Y1 - 2018/6/1

N2 - 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 O(n4). 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 isospec- tral 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.

AB - 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 O(n4). 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 isospec- tral 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.

KW - Adjacency matrix

KW - Directed graph

KW - Graph

KW - Graph isomorphism

KW - Jordan form of matrix

KW - Similarity matrices

UR - http://www.scopus.com/inward/record.url?scp=85051398016&partnerID=8YFLogxK

U2 - 10.17223/20710410/40/7

DO - 10.17223/20710410/40/7

M3 - Article

AN - SCOPUS:85051398016

SP - 87

EP - 99

JO - Prikladnaya Diskretnaya Matematika

JF - Prikladnaya Diskretnaya Matematika

SN - 2071-0410

IS - 40

ER -

ID: 36981011