EN|RU

Том 22, номер 1, 2015 г., cтр. 19-31

УДК 519.176
А. Б. Дайняк, А. Д. Курносов
Об одной экстремальной обратной задаче теории графов

Аннотация:
Рассматривается задача построения графа, имеющего заданное количество независимых множеств. Получены оценки на количество вершин в двудольных графах с предписанным числом независимых множеств и числом максимальных по включению независимых множеств.
Ил. 3, библиогр. 13.

Ключевые слова: обратная задача, независимое множество, двудольный граф.

DOI: 10.17377/daio.2015.22.445

Александр Борисович Дайняк 1
Артём Дмитриевич Курносов 1

1. Московский физико-технический институт,
Институтский пер., 9, 141700, Долгопрудный, Россия
е-mail: dainiak@phystech.edu, kurnosov@phystech.edu

Статья поступила 11 марта 2014 г.
Исправленный вариант — 12 сентября 2014 г.

Литература

[1] Czabarka É., Székely L., Wagner S. The inverse problem for certain tree parameters // Discrete Appl. Math. 2009. Vol. 157, No. 15. P. 3314–3319.

[2] Erdös P., Gallai T. Gráfok előírt fokú pontokkal // Mat. Lapok. 1960. Vol. 11. P. 264–274.

[3] Havel V., Poznámka o existenci konečných grafů Časopis pro pěstování matematiky. 1955. Vol. 80, No. 4. P. 477–480.

[4] Linek V. Bipartite graphs can have any number of independent sets // Discrete Math. 1989. Vol. 76, No. 2. P. 131–136.

[5] Wagner S. A class of trees and its Wiener index // Acta Appl. Math. 2006. Vol. 91, No. 2. P. 119–132.

[6] Wang H., YuG. All but 49 numbers are Wiener indices of trees // Acta Appl. Math. 2006. Vol. 92, No. 1. P. 15–20.

 © Институт математики им. С. Л. Соболева, 2015