首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号