|
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.
Received: 02.12.2014
Citation:
E. A. Bespalov, D. S. Krotov, “On one test for the switching separability of graphs modulo $q$”, Sibirsk. Mat. Zh., 57:1 (2016), 10–24; Siberian Math. J., 57:1 (2016), 7–17
Linking options:
https://www.mathnet.ru/eng/smj2725 https://www.mathnet.ru/eng/smj/v57/i1/p10
|
Statistics & downloads: |
Abstract page: | 256 | Full-text PDF : | 71 | References: | 46 | First page: | 5 |
|