Abstract: Рассматриваются графы, ребра которых помечены числами (весами) от 1 до q-1 (нуль соответствует отсутствию ребра). Граф называется аддитивным, если вершины можно пометить таким образом, что для любых двух несмежных вершин сумма меток по модулю q равна нулю, а для смежных – весу соответствующего ребра. Свитчингом данного графа называется его сумма по модулю q с некоторым аддитивным графом на том же множестве вершин. Граф на n вершинах называется свитчингово разделимым, если некоторый его свитчинг не имеет компонент связности мощности больше n-2. Рассматривается следующий признак свитчинговой разделимости: если удаление любой вершины графа G приводит к свитчингово разделимому графу, то и сам граф G свитчингово разделим. Доказывается этот признак для нечетного q и характеризуется множество исключений для четного q. Устанавливается связь между свитчинговой разделимостью графа и разделимостью n-арной квазигруппы, построенной по этому графу.

Cite: Беспалов Е.А. , Кротов Д.С.
Об одном признаке свитчинговой разделимости графов по модулю q
Сибирский математический журнал. 2016. Т.57. №1. С.10-24. DOI: 10.17377/smzh.2016.57.102 РИНЦ

Translated: Bespalov E.A. , Krotov D.S.
On one test for the switching separability of graphs modulo q
Siberian Mathematical Journal. 2016. V.57. N1. P.7-17. DOI: 10.1134/s003744661601002x WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:

Dec 2, 2014

Identifiers:

Elibrary:

26236926

Citing: Пока нет цитирований

Altmetrics: