On one test for the switching separability of graphs modulo q
- Авторлар: Bespalov E.1, Krotov D.1
-
Мекемелер:
- Sobolev Institute of Mathematics
- Шығарылым: Том 57, № 1 (2016)
- Беттер: 7-17
- Бөлім: Article
- URL: https://journals.rcsi.science/0037-4466/article/view/170316
- DOI: https://doi.org/10.1134/S003744661601002X
- ID: 170316
Дәйексөз келтіру
Аннотация
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.
Негізгі сөздер
Авторлар туралы
E. Bespalov
Sobolev Institute of Mathematics
Хат алмасуға жауапты Автор.
Email: bespalovpes@mail.ru
Ресей, Novosibirsk
D. Krotov
Sobolev Institute of Mathematics
Email: bespalovpes@mail.ru
Ресей, Novosibirsk