On connection between the switching separability of a graph and its subgraphs |
| |
Authors: | D S Krotov |
| |
Institution: | 1.Sobolev Institute of Mathematics,Novosibirsk,Russia;2.Novosibirsk State University,Novosibirsk,Russia |
| |
Abstract: | A graph of order n ≥ 4 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 each odd order
greater than 4, there is a graph that is not switching separable, but removing a vertex always results in a switching separable
subgraph. We show some connection with similar facts on the separability of Boolean functions and the reducibility of n-ary quasigroups. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|