Побудова пари коспектральних 5-регулярних графів, один з яких має досконале парування, а інший – ні
Loading...
Date
2021
Authors
Соболєв, Владислав
Соломко, Вікторія
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
У цій статті розглядаються тільки прості неоріентовні графи. Проблема пошуку досконалого парування у довільному простому графі є відомою і популярною в теорії графів. Її застосовують у різноманітних сферах, таких як хімія, комбінаторика, теорія ігор тощо. Паруванням М у простому графі О називають множину попарно несуміжних ребер, тобто таких, що не мають спільних вершин. Парування називають досконалим, якщо воно покриває усі вершини графа, тобто кожна з вершин графа інцидентна рівно одному з ребер у досконалому паруванні. За теоремою Кеніга, регулярні дводольні графи додатного степеня завжди мають досконале парування. Проте графи, які не є дводольними, потребують додаткових досліджень. Мультимножину власних значень матриці суміжності називають спектром графа. Окремою цікавою задачею теорії графів є пошук попарно неізоморфних коспектральних графів, тобто неізоморфних графів з однаковим спектром. У цьому напрямі проводились дослідження щодо пошуку конкретних конструкцій коспетральних пар графів. Крім того, цікавими є знаходження коспектральних графів, які мають додаткові властивості, наприклад, знаходження коспектральних графів, для одного з яких існує досконале парування, а для другого — ні. Блазік, Камінгс і Гамерс дослідили, що для кожного к > 5 існує пара коспектральних зв’язних к-регулярних графів, де один має досконале парування, а інший — ні. При доведенні цієї теореми автори використали конструкцію перемикання Годзіла Маккея. За допомогою цієї конструкції у нашій роботі покроково описано побудову пари коспектральних зв’язних 5-регулярних графів. Для одного з побудованих графів існує досконале парування, яке наведене в цій статті. Для другого побудованого графа досконалого парування не існує. Побудовані графи мають 42 вершини і складаються з 5 блоків, що з’єднані між собою мостами. За допомогою комп’ютерних засобів обчислено спектр побудованих графів. Таким чином перевірено, що пара справді є коспектральною.
The problem of finding a perfect matching in an arbitrary simple graph is well known and popular in graph theory. It is used in various fields, such as chemistry, combinatorics, game theory etc. The matching of M in a simple graph G is a set of pairwise nonadjacent edges, ie, those that do not have common vertices. Matching is called perfect if it covers all vertices of the graph, ie each of the vertices of the graph is incidental to exactly one of the edges. By Koenig’s theorem, regular bipartite graphs of positive degree always have perfect matching. However, graphs that are not bipartite need further- research. Another interesting problem of graph theory is the search for pairwise nonisomorphic cospectral graphs. In addition, it is interesting to find cospectral graphs that have additional properties. For example, finding cospectral graphs with and without a perfect matching. The fact that for each k > 5 there is a pair of cospectral connected k-regular graphs with and without a perfect matching had been investigated by Blazsik, Cummings and Haemers. The pair of cospectral connected 5-regular graphs with and without a perfect matching is constructed by using Godsil-McKay switching in the paper.
The problem of finding a perfect matching in an arbitrary simple graph is well known and popular in graph theory. It is used in various fields, such as chemistry, combinatorics, game theory etc. The matching of M in a simple graph G is a set of pairwise nonadjacent edges, ie, those that do not have common vertices. Matching is called perfect if it covers all vertices of the graph, ie each of the vertices of the graph is incidental to exactly one of the edges. By Koenig’s theorem, regular bipartite graphs of positive degree always have perfect matching. However, graphs that are not bipartite need further- research. Another interesting problem of graph theory is the search for pairwise nonisomorphic cospectral graphs. In addition, it is interesting to find cospectral graphs that have additional properties. For example, finding cospectral graphs with and without a perfect matching. The fact that for each k > 5 there is a pair of cospectral connected k-regular graphs with and without a perfect matching had been investigated by Blazsik, Cummings and Haemers. The pair of cospectral connected 5-regular graphs with and without a perfect matching is constructed by using Godsil-McKay switching in the paper.
Description
Keywords
коспектральні графи, регулярний граф, досконале парування, перемикання Годзіла-Маккея, стаття, cospectral graphs, regular graph, perfect matching, Godsil-McKay switching
Citation
Соболєв В. О. Побудова пари коспектральних 5-регулярних графів, один з яких має досконале парування, а інший – ні / Соболєв В. О., Соломко В. О. // Могилянський математичний журнал. - 2021. - Т. 4. - С. 24-27. - https://doi.org/10.18523/2617-70804202124-27