Volume 17, No 2, 2010, P. 4656
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 modulo2 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 switchingseparable subgraph, then the graph itself is switching separable. On the other hand, for every odd order there exists a nonswitchingseparable graph such that removal of any one vertex gives a switchingseparable subgraph. We also show connections with similar facts for the separability of Boolean functions and
nary quasigroups.
Ill. 1, bibl. 6.
Keywords: graph connectivity, graph switching, nary quasigroups, reducibility, Seidel switching, separability, twographs.
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
email: krotov@math.nsc.ru
