DOI

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

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Обработка сигналов
  • Дискретная математика и комбинаторика
  • Математика и теория расчета
  • Прикладная математика

ID: 36981011