Volume 17, No 2, 2010, P. 46-56
D. S. Krotov
On a connection between the switching separability of a graph and of its subgraphs
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
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
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia