Реферат: Граф порядка 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

Даты:

Поступила в редакцию:

1 окт. 2009 г.

Идентификаторы БД:

РИНЦ:

13621620

Цитирование в БД:

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