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

Simple item page
dc.contributor.authorСоболєв, Владислав
dc.contributor.authorСоломко, Вікторія
dc.date.accessioned2022-05-27T20:06:18Z
dc.date.available2022-05-27T20:06:18Z
dc.date.issued2021
dc.description.abstractУ цій статті розглядаються тільки прості неоріентовні графи. Проблема пошуку досконалого парування у довільному простому графі є відомою і популярною в теорії графів. Її застосовують у різноманітних сферах, таких як хімія, комбінаторика, теорія ігор тощо. Паруванням М у простому графі О називають множину попарно несуміжних ребер, тобто таких, що не мають спільних вершин. Парування називають досконалим, якщо воно покриває усі вершини графа, тобто кожна з вершин графа інцидентна рівно одному з ребер у досконалому паруванні. За теоремою Кеніга, регулярні дводольні графи додатного степеня завжди мають досконале парування. Проте графи, які не є дводольними, потребують додаткових досліджень. Мультимножину власних значень матриці суміжності називають спектром графа. Окремою цікавою задачею теорії графів є пошук попарно неізоморфних коспектральних графів, тобто неізоморфних графів з однаковим спектром. У цьому напрямі проводились дослідження щодо пошуку конкретних конструкцій коспетральних пар графів. Крім того, цікавими є знаходження коспектральних графів, які мають додаткові властивості, наприклад, знаходження коспектральних графів, для одного з яких існує досконале парування, а для другого — ні. Блазік, Камінгс і Гамерс дослідили, що для кожного к > 5 існує пара коспектральних зв’язних к-регулярних графів, де один має досконале парування, а інший — ні. При доведенні цієї теореми автори використали конструкцію перемикання Годзіла Маккея. За допомогою цієї конструкції у нашій роботі покроково описано побудову пари коспектральних зв’язних 5-регулярних графів. Для одного з побудованих графів існує досконале парування, яке наведене в цій статті. Для другого побудованого графа досконалого парування не існує. Побудовані графи мають 42 вершини і складаються з 5 блоків, що з’єднані між собою мостами. За допомогою комп’ютерних засобів обчислено спектр побудованих графів. Таким чином перевірено, що пара справді є коспектральною.uk_UA
dc.description.abstractThe 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.en_US
dc.identifier.citationСоболєв В. О. Побудова пари коспектральних 5-регулярних графів, один з яких має досконале парування, а інший – ні / Соболєв В. О., Соломко В. О. // Могилянський математичний журнал. - 2021. - Т. 4. - С. 24-27. - https://doi.org/10.18523/2617-70804202124-27uk_UA
dc.identifier.issn2617-7080
dc.identifier.issn2663-0648
dc.identifier.urihttps://doi.org/10.18523/2617-70804202124-27
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/23008
dc.language.isoukuk_UA
dc.relation.sourceМогилянський математичний журналuk_UA
dc.statusfirst publisheduk_UA
dc.subjectкоспектральні графиuk_UA
dc.subjectрегулярний графuk_UA
dc.subjectдосконале паруванняuk_UA
dc.subjectперемикання Годзіла-Маккеяuk_UA
dc.subjectстаттяuk_UA
dc.subjectcospectral graphsen_US
dc.subjectregular graphen_US
dc.subjectperfect matchingen_US
dc.subjectGodsil-McKay switchingen_US
dc.titleПобудова пари коспектральних 5-регулярних графів, один з яких має досконале парування, а інший – ніuk_UA
dc.title.alternativeConstructing the mate of cospectral 5-regular graphs with and without a perfect matchingen_US
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Sobolev_Solomko_Pobudova_pary_kospektralnykh_5-rehuliarnykh_hrafiv_odyn_z_yakykh_maie_doskonale_paruvannia_a_inshyi_ni.pdf
Size:
333.36 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Том 4
Факультет інформатики