Volume 17, No 2, 2010, P. 46-56

UDC 519.173.1
D. S. Krotov
On a connection between the switching separability of a graph and of its subgraphs

Abstract:
A graph of order n ≥ 4 is called switching separable if the modulo-2 sum with some complete bipartite graph on the same vertex set results in a graph consisting of two mutually independent subgraphs of orders at least two. We prove that if removal of one or two vertices of the graph always results in a switching-separable subgraph, then the graph itself is switching separable. On the other hand, for every odd order there exists a nonswitching-separable graph such that removal of any one vertex gives a switching-separable subgraph. We also show connections with similar facts for the separability of Boolean functions and
n-ary quasigroups.
Ill. 1, bibl. 6.

Keywords: graph connectivity, graph switching, n-ary quasigroups, reducibility, Seidel switching, separability, two-graphs.

Krotov Denis Stanislavovich ^1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: krotov@math.nsc.ru