On one test for the switching separability of graphs modulo $q$
E. A. Bespalov,
D. S. Krotov Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia
Abstract:
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.
Keywords:
Seidel switching, separability, $n$-ary quasigroup.
UDC:
519.143 Received: 02.12.2014
DOI:
10.17377/smzh.2016.57.102