On connection between the switching separability of a graph and its subgraphs | Sciact - Система учета научной деятельности ИМ СО РАН

On connection between the switching separability of a graph and its subgraphs Научная публикация

Журнал

Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797

Вых. Данные

Год: 2011, Том: 5, Номер: 2, Страницы: 240-246 Страниц : 7 DOI: 10.1134/s1990478911020116

Ключевые слова

two-graph, reducibility, separability, graph switching, Seidel switching, graph connectivity, n-ary quasigroup

Авторы

Krotov D.S. ^1,2

Организации

1	Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090 Russia
2	Novosibirsk State University, ul. Pirogova 2, 630090 Novosibirsk, Russia

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.

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

Кротов Д.С.
О связи свитчинговой разделимости графа и его подграфов
Дискретный анализ и исследование операций. 2010. Т.17. №2. С.46-56. РИНЦ

Поступила в редакцию:	1 окт. 2009 г.
Опубликована online:	31 мая 2011 г.

Scopus:	2-s2.0-79957929118
РИНЦ:	16989459
OpenAlex:	W3099408188

БД	Цитирований
Scopus	1
РИНЦ	1
OpenAlex	2