{
  "id": "1412.2947",
  "version": "v1",
  "published": "2014-12-09T12:58:38.000Z",
  "updated": "2014-12-09T12:58:38.000Z",
  "title": "On a test on switching separability of graphs modulo $q$",
  "authors": [
    "Evgeny Bespalov",
    "Denis Krotov"
  ],
  "comment": "In Russian, 16pp",
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider the graphs whose edges are marked by the integers (weights) from $0$ to $q-1$ (zero corresponds to no-edge). Such graph is called additive if its vertices can be marked in such a way that the weight of every edge is equal to the modulo-$q$ sum of weights of the two incident vertices. By a switching of a graph we mean the modulo-$q$ sum of the graph with some additive graph on the same vertex set. A graph with $n$ vertices is called switching separable if some of its switchings does not have a connected component of order $n$ or $n-1$. We consider the following test for the switching separability: if removing any vertex of a graph $G$ results in a switching separable graph, then $G$ is switching separable itself. We prove this test for odd $q$ and characterize the exceptions when $q$ is even. We establish a connection between the switching separability of a graph and the reducibility of $(n-1)$-ary quasigroups constructed from this graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-12-09T12:58:38.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C99",
      "05B15"
    ],
    "keywords": [
      "switching separability",
      "graphs modulo",
      "switching separable",
      "incident vertices",
      "vertex set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "ru",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1412.2947B"
    }
  }
}