{
  "id": "1104.0003",
  "version": "v1",
  "published": "2011-03-31T20:00:01.000Z",
  "updated": "2011-03-31T20:00:01.000Z",
  "title": "On a connection between the switching separability of a graph and that of its subgraphs",
  "authors": [
    "Denis Krotov"
  ],
  "comment": "english: 9 pages; russian: 9 pages",
  "journal": "J. Appl. Ind. Math. 5(2) 2011, 240-246 (English); Diskretn. Anal. Issled. Oper. 17(2) 2010, 46-56 (Russian)",
  "doi": "10.1134/S1990478911020116",
  "categories": [
    "math.CO"
  ],
  "abstract": "A graph of order $n>3$ is called {switching separable} if its modulo-2 sum with some complete bipartite graph on the same set of vertices is divided into two mutually independent subgraphs, each having at least two vertices. We prove the following: if removing any one or two vertices of a graph always results in a switching separable subgraph, then the graph itself is switching separable. On the other hand, for every odd order greater than 4, there is a graph that is not switching separable, but removing any vertex always results in a switching separable subgraph. We show a connection with similar facts on the separability of Boolean functions and reducibility of $n$-ary quasigroups. Keywords: two-graph, reducibility, separability, graph switching, Seidel switching, graph connectivity, $n$-ary quasigroup",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-03-31T20:00:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C99"
    ],
    "keywords": [
      "switching separability",
      "connection",
      "ary quasigroup",
      "switching separable subgraph",
      "odd order greater"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1104.0003K"
    }
  }
}