Побудова пари коспектральних 5-регулярних графів, один з яких має досконале парування, а інший – ні

Автор(и)

  • Viktoriia Solomko Національний університет «Києво-Могилянська академія», Ukraine
  • Vladyslav Sobolev Національний університет «Києво-Могилянська академія», Ukraine

DOI:

https://doi.org/10.18523/2617-70804202124-27

Ключові слова:

коспектральні графи, регулярний граф, досконале парування, перемикання Годзіла-Маккея

Анотація

У цій статті розглядаються тільки прості неорієнтовні графи. Проблема пошуку досконалого парування у довiльному простому графi є відомою і популярною в теорії графів. Її застосовують у рiзноманiтних сферах, таких як хiмiя, комбiнаторика, теорiя iгор тощо. Паруванням M у простому графi G називають множину попарно несумiжних ребер, тобто таких, що не мають спiльних вершин.
Парування називають досконалим, якщо воно покриває усi вершини графа, тобто кожна з вершин графа iнцидентна рiвно одному з ребер у досконалому паруваннi. За теоремою Кенiга, регулярнi дводольнi графи додатного степеня завжди мають досконале парування. Проте графи, які не є дводольними, потребують додаткових досліджень.
Мультимножину власних значень матриці суміжності називають спектром графа. Окремою цікавою задачею теорії графів є пошук попарно неізоморфних коспектральних графів, тобто неізоморфних графів з однаковим спектром. У цьому напрямі проводились дослідження щодо пошуку конкретних конструкцій коспетральних пар графів. Крім того, цікавими є знаходження коспектральних графів, які мають додаткові властивості, наприклад, знаходження коспектральних графів, для одного з яких існує досконале парування, а для другого --- ні.

Блазік, Камінгс і Гамерс дослідили, що для кожного існує пара коспектральних зв'язних k-регулярних графів, де один має досконале парування, а інший --- ні. При доведенні цієї теореми автори використали конструкцію перемикання Годзiла--Маккея. За допомогою цієї конструкції у нашій роботі покроково описано побудову пари коспектральних зв’язних 5-регулярних графiв. Для одного з побудованих графів існує досконале парування, яке наведене в цій статті. Для другого побудованого графа досконалого парування не існує. Побудовані графи мають 42 вершини і складаються з 5 блоків, що з’єднані між собою мостами. За допомогою комп’ютерних засобів обчислено спектр побудованих графів. Таким чином перевірено, що пара справді є коспектральною.

Біографії авторів

Viktoriia Solomko , Національний університет «Києво-Могилянська академія»

Кандидат фіз.-мат. наук, старший викладач кафедри математики Національного університету “Києво-Могилянська академія”. Сфера наукових інтересів: спектральна теорія графів.

 

Vladyslav Sobolev, Національний університет «Києво-Могилянська академія»

Студент 3-го року навчання бакалаврської програми за спеціальністю “Комп'ютерні науки” Національного університету “Києво-Могилянська академія”. Сфера наукових інтересів: абстрактна алгебра, теорія зображень.

vladyslav.soboliev@ukma.edu.ua

Посилання

S. M. Cioaba, D. Gregory and W. H. Haemers, "Matching in regular graphs from eigenvalues", Journal of Combinatorial Theory. 99, 287–297 (2009).

E. R. van Dam and W. H. Haemers, "Which graphs are determined by their spectrum?", Linear Algebra and its Applications. 373, 241–272 (2003).

Z. L. Blazsik, J. Cummings and W. H. Haemers, "Cospectral regular graphs with and without a perfect matching", Discrete Mathematics. 338, 199–201 (2015).

A. E. Brouwer and W. H. Haemers, Spectra of Graphs (New York, Springer, 2011), p. 250.

##submission.downloads##

Опубліковано

2022-05-19