RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2016 Volume 57, Number 1, Pages 10–24 (Mi smj2725)

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


 English version:
Siberian Mathematical Journal, 2016, 57:1, 7–17

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024