On connection between the switching separability of a graph and its subgraphs Full article
| Journal |
Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2011, Volume: 5, Number: 2, Pages: 240-246 Pages count : 7 DOI: 10.1134/s1990478911020116 | ||||
| Tags | two-graph, reducibility, separability, graph switching, Seidel switching, graph connectivity, n-ary quasigroup | ||||
| Authors |
|
||||
| Affiliations |
|
Abstract:
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 n-ary quasigroups.
Cite:
Krotov D.S.
On connection between the switching separability of a graph and its subgraphs
Journal of Applied and Industrial Mathematics. 2011. V.5. N2. P.240-246. DOI: 10.1134/s1990478911020116 Scopus РИНЦ OpenAlex
On connection between the switching separability of a graph and its subgraphs
Journal of Applied and Industrial Mathematics. 2011. V.5. N2. P.240-246. DOI: 10.1134/s1990478911020116 Scopus РИНЦ OpenAlex
Original:
Кротов Д.С.
О связи свитчинговой разделимости графа и его подграфов
Дискретный анализ и исследование операций. 2010. Т.17. №2. С.46-56. РИНЦ
О связи свитчинговой разделимости графа и его подграфов
Дискретный анализ и исследование операций. 2010. Т.17. №2. С.46-56. РИНЦ
Dates:
| Submitted: | Oct 1, 2009 |
| Published online: | May 31, 2011 |
Identifiers:
| Scopus: | 2-s2.0-79957929118 |
| Elibrary: | 16989459 |
| OpenAlex: | W3099408188 |