Вiдновлююче спектральне число графа K4
Loading...
Date
2024
Authors
Аверкін, Олександр
Тимошкевич, Лариса
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Статтю присвячено дослiдженню обернених спектральних задач для зважених графiв. Розглянуто задачу щодо вiдновлення ваг на множинi ребер графа за спектрами його iндукованих пiдграфiв. Завдяки широкому колу застосувань, оберненi спектральнi задачi активно вивчають для рiзних класiв матриць: зазвичай вони зводяться до вiдновлення матрицi (або її частини) за спектром самої матрицi чи її пiдматриць. Наша задача стосується класу нерозкладних симетричних матриць з невiд’ємними елементами та нулями на головнiй дiагоналi — матриць сумiжностi зв’язних зважених графiв. Ключовим поняттям цiєї роботи є вiдновлююче спектральне число графа Srn(G) — мiнiмальна кiлькiсть спектрiв iндукованих пiдграфiв, необхiдних для однозначного вiдновлення всiх ваг ребер графа G. Головним результатом дослiдження є знаходження точного значення Srn(K4) для повного графа на чотирьох вершинах. Одержанi результати та використанi у роботi методи можуть бути застосованi в подальших дослiдженнях, зокрема для визначення точних значень вiдновлюючого спектрального числа iнших графiв.
Description
In this work, we introduce new formulations of inverse spectral problems for weighted graphs in which certain spectral data (namely, the spectra of selected induced subgraphs) uniquely determine the edge weights of the original graph. To quantify this, we define the spectral reconstruction number of a graph Srn(G) as the minimum number of spectra of induced subgraphs required to uniquely recover all edge weights of G. Motivated by their broad range of applications, inverse spectral problems for various classes of matrices have been actively studied in the literature. These problems typically involve recovering a matrix, or part of it, from the spectrum of the matrix itself or from the spectra of its submatrices. From a matrix-theoretic perspective, the problem concerns irreducible symmetric matrices with zero diagonal and nonnegative off-diagonal entries, which are adjacency matrices of connected edge-weighted graphs. Thus, the results obtained here offer new inverse spectral formulations for this class of matrices. The main contribution of this paper is the exact determination of the spectral reconstruction number for the complete graph on four vertices.
Keywords
спектр графа, власнi числа, оберненi спектральнi задачi, зважений граф, стаття, eigenvalues, spectra of a graph, weighted graph, subgraphs of a graph
Citation
Аверкін О. С. Вiдновлююче спектральне число графа K4 / Аверкiн О. С., Тимошкевич Л. М. // Могилянський математичний журнал. - 2024. - Т. 7. - C. 9-16. - https://doi.org/10.18523/2617-7080720249-16