Беспалов Е. А., Кротов Д. С.
Об одном признаке свитчинговой разделимости графов по модулю q

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

E. A. Bespalov, D. S. Krotov
On one test for the switching separability of graphs modulo q

We consider graphs whose edges are marked by numbers (weights) from 1 to q - 1 (with zero corresponding to the absence of an edge). A graph is additive if its vertices can be marked so that, for every two nonadjacent vertices, the sum of the marks modulo q is zero, and for adjacent vertices, it equals the weight of the corresponding edge. A switching of a given graph is its sum modulo q with some additive graph on the same set of vertices. A graph on n vertices is switching separable if some of its switchings has no connected components of size greater than n - 2. We consider the following separability test: If removing any vertex from G leads to a switching separable graph then G is switching separable. We prove this test for q odd and characterize the set of exclusions for q even. Connection is established between the switching separability of a graph and the reducibility of the n-ary quasigroup constructed from the graph.

DOI 10.17377/smzh.2016.57.102
Ключевые слова: свитчинг Зейделя, разделимость, n-арные квазигруппы

Полный текст статьи / Full texts:

• PDF file
• PostScript file