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.

Cite: Bespalov E.A. , Krotov D.S.
On one test for the switching separability of graphs modulo q
Siberian Mathematical Journal. 2016. V.57. N1. P.7-17. DOI: 10.1134/s003744661601002x WOS Scopus РИНЦ OpenAlex

Original: Беспалов Е.А. , Кротов Д.С.
Об одном признаке свитчинговой разделимости графов по модулю q
Сибирский математический журнал. 2016. Т.57. №1. С.10-24. DOI: 10.17377/smzh.2016.57.102 РИНЦ

Dates:

Submitted:	Dec 2, 2014
Published online:	Mar 29, 2016

Identifiers:

Web of science:	WOS:000373234400002
Scopus:	2-s2.0-85008471286
Elibrary:	29472161
OpenAlex:	W3100811678

Citing:

DB	Citing
Elibrary	1

Altmetrics: