Том 25, номер 2, 2018 г., Стр. 101-123

УДК 519.17
Талецкий Д. С., Малышев Д. С.
О деревьях ограниченной степени с максимальным количеством наибольших независимых множеств

Аннотация:
Для любых $n$ и $d$ описана структура деревьев с максимально возможным количеством наибольших независимых множеств в классе $n$-вершинных деревьев, степень каждой вершины которых не превосходит $d$. Показано, что при всех чётных $n$ экстремальное дерево единственно, а при нечётных $n$ единственности может и не быть, причём при $d = 3$ для любого нечётного $n \ge 7$ имеется в точности $\left \lceil \dfrac{n - 3}{4} \right \rceil + 1$ экстремальных деревьев. В данной работе проблема поиска экстремальных ($n, d$)-деревьев также рассмотрена применительно к $2$-гусеницам, т. е. деревьям, в которых каждая вершина отстоит от некоторого простого пути на расстояние не более чем два. В ней для любых $n$ и $d \in$ {$3, 4$} полностью выявляются все экстремальные 2-гусеницы с $n$ вершинами, каждая из которых имеет степень не более чем $d$.
Ил. 9, библиогр. 10.

Ключевые слова: экстремальная комбинаторика, дерево, наибольшее независимое множество.

DOI: 10.17377/daio.2018.25.591

Талецкий Дмитрий Сергеевич ¹
Малышев Дмитрий Сергеевич ^2,1
1. Нижегородский гос. университет им. Н. И. Лобачевского,
пр. Гагарина, 23, 603950 Нижний Новгород, Россия
2. Национальный исследовательский университет «Высшая школа экономики»,
ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
е-mail: dmitalmail@gmail.com, dsmalyshev@rambler.ru

Статья поступила 29 сентября 2017 г.

Литература

[1] Andriantiana E. Energy, Hosoya index and Merrifield–Simmons index of trees with prescribed degree sequence // Discrete Appl. Math. 2013. Vol. 161, No. 6. P. 724–741.

[2] Griggs J., Grinstead C., Guichard D. The number of maximal independent sets in a connected graph // Discrete Math. 1988. Vol. 68, No. 2–3. P. 211–220.

[3] Heuberger C., Wagner S. Maximizing the number of independent subsets over trees with bounded degree // J. Graph Theory. 2008. Vol. 58, No. 1. P. 49–68.

[4] Hujter M., Tuza Z. The number of maximal independent sets in triangle-free graphs // SIAM J. Discrete Math. 1993. Vol. 6, No. 2. P. 284–288.

[5] Jou M., Chang G. Maximal independent sets in graphs with at most one cycle // Discrete Appl. Math. 1997. Vol. 79, No. 1–3. P. 67–73.

[6] Jou M., Chang G. The number of maximum independent sets in graphs // J. Graph Theory. 2000. Vol. 4, No. 4. P. 685–695.

[7] Liu J. Maximal independent sets in bipartite graphs // J. Graph Theory. 1993. Vol. 17, No. 4. P. 495–507.

[8] Moon J., Moser L. On cliques in graphs // Isr. J. Math. 1965. Vol. 3. P. 23–28.

[9] Wilf H. The number of maximal independent sets in a tree // SIAM J. Algebraic Discrete Methods. 1986. Vol. 7, No. 1. P. 125–130.

[10] Zito J. The structure and maximum number of maximum independent sets in trees // J. Graph Theory. 1991. Vol. 15, No. 2. P. 207–221.