Том 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. |