On a connection between the switching separability of a graph and that of its subgraphs

zbMATH Open1249.05184arXiv1104.0003MaRDI QIDQ3115214

Denis S. Krotov

Publication date: 20 February 2012

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

Full work available at URL: https://arxiv.org/abs/1104.0003

zbMATH Keywords

reducibilitySeidel switchingseparabilitygraph connectivitygraph switchingtwo-graphn-ary quasigroup

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Related Items (2)

On one test for the switching separability of graphs modulo \(q\) ⋮ Title not available (Why is that?)

This page was built for publication: On a connection between the switching separability of a graph and that of its subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3115214)