|
Diskretnyi Analiz i Issledovanie Operatsii, 2010, Volume 17, Issue 2, Pages 46–56
(Mi da605)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
On a connection between the switching separability of a graph and of its subgraphs
D. S. Krotovab a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
Abstract:
A graph of order $n\geq4$ 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.
Received: 01.10.2009
Citation:
D. S. Krotov, “On a connection between the switching separability of a graph and of its subgraphs”, Diskretn. Anal. Issled. Oper., 17:2 (2010), 46–56
Linking options:
https://www.mathnet.ru/eng/da605 https://www.mathnet.ru/eng/da/v17/i2/p46
|
|