Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
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.
Язык оригинала | английский |
---|---|
Страницы (с-по) | 87-99 |
Число страниц | 13 |
Журнал | Prikladnaya Diskretnaya Matematika |
Номер выпуска | 40 |
DOI | |
Состояние | Опубликовано - 1 июн 2018 |
ID: 36981011