On a test on switching separability of graphs modulo $q$

Abstract

We consider the graphs whose edges are marked by the integers (weights) from $0$ to $q-1$ (zero corresponds to no-edge). Such graph is called additive if its vertices can be marked in such a way that the weight of every edge is equal to the modulo-$q$ sum of weights of the two incident vertices. By a switching of a graph we mean the modulo-$q$ sum of the graph with some additive graph on the same vertex set. A graph with $n$ vertices is called switching separable if some of its switchings does not have a connected component of order $n$ or $n-1$. We consider the following test for the switching separability: if removing any vertex of a graph $G$ results in a switching separable graph, then $G$ is switching separable itself. We prove this test for odd $q$ and characterize the exceptions when $q$ is even. We establish a connection between the switching separability of a graph and the reducibility of $(n-1)$-ary quasigroups constructed from this graph.

In Russian, 16pp

References in corpus (6)

• n-Ary quasigroups of order 4
• Asymptotics for the number of n-quasigroups of order 4
• On irreducible n-ary quasigroups with reducible retracts
• On reducibility of n-ary quasigroups
• On connection between reducibility of an n-ary quasigroup and that of its retracts
• On a connection between the switching separability of a graph and that of its subgraphs