On one test for the switching separability of graphs modulo q
- Authors: Bespalov E.A.1, Krotov D.S.1
-
Affiliations:
- Sobolev Institute of Mathematics
- Issue: Vol 57, No 1 (2016)
- Pages: 7-17
- Section: Article
- URL: https://journals.rcsi.science/0037-4466/article/view/170316
- DOI: https://doi.org/10.1134/S003744661601002X
- ID: 170316
Cite item
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
About the authors
E. A. Bespalov
Sobolev Institute of Mathematics
Author for correspondence.
Email: bespalovpes@mail.ru
Russian Federation, Novosibirsk
D. S. Krotov
Sobolev Institute of Mathematics
Email: bespalovpes@mail.ru
Russian Federation, Novosibirsk