О связи свитчинговой разделимости графа и его подграфов

О связи свитчинговой разделимости графа и его подграфов Full article

Journal

Дискретный анализ и исследование операций
ISSN: 1560-7542

Output data

Year: 2010, Volume: 17, Number: 2, Pages: 46-56 Pages count : 11

Tags

два-граф, приводимость, разделимость, свитчинг графа, свитчинг Зейделя, связность графа, n-арная квазигруппа.

Authors

Кротов Д.С. ^1,2

Affiliations

1	Институт математики им. С.Л. Соболева СО РАН
2	Новосибирский государственный университет

Граф порядка n≥4 называется свитчингово разделимым, если его сумма по модулю два с некоторым полным двудольным графом на том же множестве вершин разделена на два не связанных между собой подграфа на двух или более вершинах. Доказано, что если удалением одной или двух вершин из данного графа мы получаем только свитчингово разделимые подграфы, то и сам граф свитчингово разделим. С другой стороны, существует граф любого нечётного порядка, который сам не является свитчингово разделимым, а удаление любой вершины приводит к свитчингово разделимому подграфу. Показана связь с аналогичными фактами для разделимости булевых функций и n-арных квазигрупп.

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

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

Submitted:

Oct 1, 2009

Elibrary:

13621620

DB	Citing
Elibrary	2