Том 23, номер 1, 2016 г., Стр. 5-16

УДК 519.17
Алексеев В. Е., Захарова Д. В.
Независимые множества в графах без поддеревьев с большим числом листьев

Аннотация:
Поддерево графа называется вписанным, если никакие три вершины этого поддерева не порождают треугольника в графе. Доказывается, что при любом фиксированном k задача о независимом множестве разрешима за полиномиальное время для графов, входящих в один из следующих классов: 1) графы, не имеющие поддеревьев с k листьями, 2) субкубические графы, не имеющие вписанных поддеревьев с k листьями, 3) графы со степенями, не превосходящими k, не имеющие порождённых поддеревьев с 4 листьями.
Ил. 1, библиогр. 12.

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

DOI: 10.17377/daio.2016.23.499

Алексеев Владимир Евгеньевич ¹
Захарова Дарья Владимировна ¹
1. Нижегородский гос. университет им. Н. И. Лобачевского,
пр. Гагарина, 23, корп. 2, 603950, Нижний Новгород, Россия
е-mail: aleve@rambler.ru, dvzakh@rambler.ru

Статья поступила 11 июня 2015 г.
Исправленный вариант — 25 июня 2015 г.

Литература

[1] Алексеев В. Е. Полиномиальный алгоритм для нахождения наибольших независимых множеств в графах без вилок // Дискрет. анализ и исслед. операций. 1999. Т. 6, № 4. С. 3–19.

[2] Алексеев В. Е., Захарова Д. В. Независимые множества в графах с ограниченными минорами расширенной матрицы инцидентности //Дискрет. анализ и исслед. операций. 2010. Т. 17, № 1. С. 3–10.

[3] Алексеев В. Е., Коробицын Д. В. О сложности некоторых задач на наследственных классах графов // Дискрет. математика. 1992. Т. 4, вып. 4. С. 34–40.

[4] Алексеев В. Е., Малышев Д. С. Классы планарных графов с полиномиально разрешимой задачей о независимом множестве // Дискрет. анализ и исслед. операций. 2008. Т. 15, № 1. С. 3–10.

[5] Алексеев В. Е., Таланов В. А. Графы и алгоритмы. Структуры данных. Модели вычислений. М.: Бином. Лаборатория знаний, 2006. 319 с.

[6] Банкевич А. В., Карпов Д. В. Оценки количества висячих вершин в остовных деревьях // Зап. науч. семинаров ПОМИ. 2011. Т. 391. С. 18–34.

[7] Захарова Д. В. Взвешенные независимые множества в графах с ограниченными минорами расширенной матрицы инцидентности // Мат. Х Междунар. семинара «Дискретная математика и её приложения» (Москва, 1–6 февраля 2010 г.). М.: Изд-во мехмата МГУ, 2010. С. 303–305.

[8] Малышев Д. С. Классы субкубических планарных графов, для которых задача о независимом множестве является полиномиально разрешимой // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 3. С. 26–44.

[9] Шевченко В. Н. Качественные вопросы целочисленного программирования. М.: Наука, 1995. 190 с.

[10] Erdös P., Szekeres G. A combinatorial problem in geometry // Compos. Math. 1935. Vol. 2. P. 463–470.

[11] Minty G. J. On maximal independent sets of vertices in claw-free graphs // J. Comb. Theory, Ser. B. 1980. Vol. 28. P. 284–304.

[12] Sbihi N. Algorithme de recherche d’un stable de cardinalitґe maximum dans un graphe sans ґetoile // Discrete Math. 1980. Vol. 29, No. 1. P. 53–76.