О деревьях заданного диаметра с экстремальным количеством k-дистанционных независимых множеств

О деревьях заданного диаметра с экстремальным количеством $k$-дистанционных независимых множеств 

Талецкий Д. С.
Дискретный анализ и исследование операций, 30, 3, 111–131 (2023)
Скачать статью

УДК 519.17 
DOI: 10.33048/daio.2023.30.755

Аннотация:

Множество вершин графа называется $k$-дистанционным независимым, если расстояние между любыми двумя его вершинами больше некоторого целого числа $k \ge 1$. В работе рассматривается задача описания $n$-вершинных деревьев фиксированного диаметра $d$, содержащих максимально и минимально возможное число $k$-дистанционных независимых множеств среди всех таких деревьев. Задача на максимум решается для случая $1 < k < d \le 5$ при всех достаточно больших значениях $n$. Задача на минимум существенно более простая и решается для всех значений параметров $1 < k < d < n$.  
Ил. 4, библиогр. 10.

Литература:
  1. Pedersen A. S., Vestergaard P. D. An upper bound on the number of independent sets in a tree // Ars Comb. 2007. V. 84. P. 85–96.
     
  2. Frendrup A., Pedersen A. S., Sapozhenko A. A., Vestergaard P. D. Merrifield–Simmons index and minimum number of independent sets in short trees // Ars Comb. 2013. V. 111. P. 85–95.
     
  3. Дайняк А. Б. О числе независимых множеств в деревьях фиксированного диаметра // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 2. С. 61–73.
     
  4. Талецкий Д. С. Деревья диаметра 6 и 7 с минимальным количеством независимых множеств // Мат. заметки. 2021. Т. 109, № 2. С. 276–289.
     
  5. Atkinson G., Frieze A. On the $b$-independence number of sparse random graphs // Comb. Probab. Comput. 2004. V. 13, No. 3. P. 295–309.
     
  6. Abiad A., Cioabă S. M., Tait M. Spectral bounds for the $k$-independence number of a graph // Linear Algebra Appl. 2016. V. 510. P. 160–170.
     
  7. Bouchou A., Blidia M. On the $k$-independence number in graphs // Australas. J. Comb. 2014. V. 59, No. 2. P. 311–322.
     
  8. O S., Shi Y., Taoqiu Z. Sharp upper bounds on the $k$-independence number in graphs with given minimum and maximum degree // Graphs Comb. 2020. V. 37. P. 393–408.
     
  9. Li Z., Wu B. The $k$-independence number of $t$-connected graphs // Appl. Math. Comput. 2021. V. 409. Paper ID 126412. 4 p.
     
  10. Jou M. J., Lin J. J. Characterization of the distance-$k$ independent dominating sets of the $n$-path // Int. J. Contemp. Math. Sci. 2018. V. 13, No. 6. P. 231–238.

Исследование выполнено при финансовой поддержке Российского научного фонда (проект № 21–11–00194).

Талецкий Дмитрий Сергеевич
  1. Национальный исследовательский университет «Высшая школа экономики», 
    ул. Большая Печерская, 25/12, 603155 Нижний Новгород, Россия
  2. Нижегородский гос. университет им. Н. И. Лобачевского, 
    пр. Гагарина, 23, 603950 Нижний Новгород, Россия

E-mail: dmitalmail@gmail.com

Статья поступила 20 октября 2022 г. 
После доработки — 2 мая 2023 г. 
Принята к публикации 11 мая 2023 г.

Abstract:

The set of vertices of a graph is called distance-$k$ independent if the distance between any two of its vertices is greater than some integer $k \ge 1$. In this paper we describe $n$-vertex trees with a given diameter $d$ which have maximum and minimum possible number of distance-$k$ independent sets among all such trees. The maximum problem is solved for the case $1 < k < d \le 5$. The minimum problem is significantly more simple and is solved for all $1 < k < d < n$. 
Illustr. 4, bibliogr. 10.

References:
  1. A. S. Pedersen and P. D. Vestergaard, An upper bound on the number of independent sets in a tree, Ars Comb. 84, 85–96 (2007).
     
  2. A. Frendrup, A. S. Pedersen, A. A. Sapozhenko, and P. D. Vestergaard, Merrifield–Simmons index and minimum number of independent sets in short trees, Ars Comb. 111, 85–95 (2013).
     
  3. A. B. Dainyak, On the number of independent sets in the trees of a fixed diameter, Diskretn. Anal. Issled. Oper. 16 (2), 61–73 (2009) [Russian] [J. Appl. Ind. Math. 4 (2), 163–171 (2010)].
     
  4. D. S. Taletskii, Trees of diameter 6 and 7 with minimum number of independent sets, Mat. Zametki 109 (2), 276–289 (2021) [Russian] [Math. Notes 109 (1–2), 280–291 (2021)].
     
  5. G. Atkinson and A. Frieze, On the $b$-independence number of sparse random graphs, Comb. Probab. Comput. 13 (3), 295–309 (2004).
     
  6. A. Abiad, S. M. Cioabă, and M. Tait, Spectral bounds for the $k$-independence number of a graph, Linear Algebra Appl. 510, 160–170 (2016).
     
  7. A. Bouchou and M. Blidia, On the $k$-independence number in graphs, Australas. J. Comb. 59 (2), 311–322 (2014).
     
  8. S. O, Y. Shi, and Z. Taoqiu, Sharp upper bounds on the $k$-independence number in graphs with given minimum and maximum degree, Graphs Comb. 37, 393–408 (2020).
     
  9. Z. Li and B. Wu, The $k$-independence number of $t$-connected graphs, Appl. Math. Comput. 409, ID 126412, 4 p. (2021).
     
  10. M. J. Jou and J. J. Lin, Characterization of the distance-$k$ independent dominating sets of the $n$-path, Int. J. Contemp. Math. Sci. 13 (6), 231–238 (2018).