|
Дискретный анализ и исследование операций, 2010, том 17, выпуск 2, страницы 46–56
(Mi da605)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
О связи свитчинговой разделимости графа и его подграфов
Д. С. Кротовab a Институт математики им. С. Л. Соболева СО РАН, Новосибирск, Россия
b Новосибирский гос. университет, Новосибирск, Россия
Аннотация:
Граф порядка $n\geq4$ называется свитчингово разделимым, если его сумма по модулю два с некоторым полным двудольным графом на том же множестве вершин разделена на два не связанных между собой подграфа на двух или более вершинах. Доказано, что если удалением одной или двух вершин из данного графа мы получаем только свитчингово разделимые подграфы, то и сам граф свитчингово разделим. С другой стороны, существует граф любого нечётного порядка, который сам не является свитчингово разделимым, а удаление любой вершины приводит к свитчингово разделимому подграфу. Показана связь с аналогичными фактами для разделимости булевых функций и $n$-арных квазигрупп. Иллюстр. 1, библиогр. 6.
Ключевые слова:
два-граф, приводимость, разделимость, свитчинг графа, свитчинг Зейделя, связность графа, $n$-арная квазигруппа.
Статья поступила: 01.10.2009
Образец цитирования:
Д. С. Кротов, “О связи свитчинговой разделимости графа и его подграфов”, Дискретн. анализ и исслед. опер., 17:2 (2010), 46–56
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da605 https://www.mathnet.ru/rus/da/v17/i2/p46
|
Статистика просмотров: |
Страница аннотации: | 311 | PDF полного текста: | 104 | Список литературы: | 54 | Первая страница: | 1 |
|