Том 17, номер 2, 2010 г., Стр. 46-56

УДК 519.173.1
Кротов Д. С.
О связи свитчинговой разделимости графа и его подграфов

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

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

Кротов Денис Станиславович ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: krotov@math.nsc.ru

Статья поступила 1 октября 2009 г.