О соотношении двух классов экстремальных деревьев с заданной степенной последовательностью

О соотношении двух классов экстремальных деревьев с заданной степенной последовательностью

Круподерова С. А., Курносов А. Д.
Дискретный анализ и исследование операций, 32, 2, 72-87 (2025)
Скачать статью

УДК 519.172.1 
DOI: 10.33048/daio.2025.32.826

Аннотация:

Вершины графа, смежные с листьями, назовём опорными. В работе исследуется, как могут соотноситься между собой два класса экстремальных деревьев, имеющих одну и ту же последовательность степеней вершин: класс деревьев, реализующих минимум числа опорных вершин и класс деревьев, реализующих минимум числа доминирования. Заметную роль здесь играют две величины, определяемые через степенную последовательность: число Слэйтера, предложенное Слэйтером в качестве нижней оценки числа доминирования, и предложенная Курносовым нижняя оценка числа опорных вершин дерева. В работе полностью решена задача сравнения классов в случае, когда максимумом из двух величин является вторая. 

Ил. 2, библиогр. 14.

Литература:
  1. Andriantiana E. Energy, Hosoya index and Merrifield–Simmons index of trees with prescribed degree sequence // Discrete Appl. Math. 2013. V. 161, No. 6. P. 724–741.
     
  2. Bessy S., Rautenbach D. Extremal values of the chromatic number for a given degree sequence // Graphs Comb. 2017. V. 33, No. 4. P. 789–799.
     
  3. Rao A. R. The clique number of a graph with given degree sequence // Graph Theory. Proc. Symp. (Calcutta, India, Dec. 20–25, 1976). New Delhi: MacMillan India, 1979. P. 251–267. (ISI Lect. Notes; V. 4).
     
  4. Favaron O., Mahéo M., Saclé J. On the residue of a graph // J. Graph Theory. 1991. V. 15, No. 1. P. 39–64.
     
  5. Griggs R., Kleitman D. Independence and the Havel–Hakimi residue // Discrete Math. 1994. V. 127. P. 209–212. 
     
  6. Pepper R. On the annihilation number of a graph // Proc. 15th Am. Conf. Applied Mathematics (Houston, USA, Apr. 30 – May 2, 2009). Stevens Point, WI: WSEAS, 2009. P. 217–220.
     
  7. Slater P. J. Locating dominating sets and locating-dominating sets // Proc. 7th Quad. Int. Conf. Theory and Applications of Graphs (Kalamazoo, MI, USA, June 1–5, 1992). V. 2. New York: Wiley, 1995. P. 1073–1079.
     
  8. Gentner M., Henning M., Rautenbach D. Largest domination number and smallest independence number of forests with given degree sequence // Discrete Appl. Math. 2016. V. 206. P. 181–187.
     
  9. Gentner M., Henning M., Rautenbach D. Smallest domination number and largest independence number of graphs and forests with given degree sequence // J. Graph Theory. 2018. V. 88, No. 1. P. 131–145.
     
  10. Курносов А. Д. Множество всех возможных значений числа доминирования в деревьях с заданной степенной последовательностью // Дискрет. анализ и исслед. операций. 2020. Т. 27, № 1. С. 61–87.
     
  11. Курносов А. Д. О нижней оценке числа связного доминирования в графах с фиксированной степенной последовательностью // Тр. МФТИ. 2020. Т. 12, № 2. С. 40–54.
     
  12. DeLavina E., Larson C. E., Pepper R., Waller B., Favaron O. On total domination and support vertices of a tree // AKCE Int. J. Graphs Comb. 2010. V. 7, No. 1. P. 85–95.
     
  13. Desormeaux W. J., Haynes T. W., Henning M. A. Improved bounds on the domination number of a tree // Discrete Appl. Math. 2014. V. 177. P. 88–94.
     
  14. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука. Физматлит, 1990. 384 с.

Исследование выполнено за счёт бюджета Московского физико-технического института (национального исследовательского университета). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Круподерова Софья Андреевна
  1. Московский физико-технический институт (национальный исследовательский университет), 
    Институтский пер., 9, 141700 Долгопрудный, Россия

E-mail: krupoderova.sa@phystech.edu

Курносов Артём Дмитриевич
  1. Московский физико-технический институт (национальный исследовательский университет), 
    Институтский пер., 9, 141700 Долгопрудный, Россия

E-mail: kurnosov@phystech.edu

Статья поступила 29 января 2025 г.
После доработки — 15 марта 2025 г.
Принята к публикации 22 марта 2025 г.

Abstract:

A non-pendant vertex of a graph is called a support vertex if it is adjacent to a leaf. This paper examines the relationship between two classes of extremal trees with the same vertex degree sequence: the class of trees minimizing the number of support vertices and the class of trees minimizing the domination number. Two values defined in terms of a degree sequence play a significant role here: the Slater number, proposed by Slater as a lower bound for the domination number, and the lower bound for the number of support vertices of a tree, proposed by Kurnosov. This paper completely solves the problem of comparing the classes in the case where the maximum of the two values is the latter. 

Illustr. 2, bibliogr. 14.

References:
  1. E. Andriantiana, Energy, Hosoya index and Merrifield–Simmons index of trees with prescribed degree sequence, Discrete Appl. Math. 161 (6), 724–741 (2013).
     
  2. S. Bessy and D. Rautenbach, Extremal values of the chromatic number for a given degree sequence, Graphs Comb. 33 (4), 789–799 (2017).
     
  3. A. R. Rao, The clique number of a graph with given degree sequence, in Graph Theory (Proc. Symp., Calcutta, India, Dec. 20–25, 1976) (MacMillan India, New Delhi, 1979), pp. 251–267 (ISI Lect. Notes, Vol. 4).
     
  4. O. Favaron, M. Mahéo, and J. Saclé, On the residue of a graph, J. Graph Theory 15 (1), 39–64 (1991).
     
  5. R. Griggs and D. Kleitman, Independence and the Havel–Hakimi residue, Discrete Math. 127, 209–212 (1994). 
     
  6. R. Pepper, On the annihilation number of a graph, in Proc. 15th Am. Conf. Applied Mathematics, Houston, USA, Apr. 30 – May 2, 2009 (WSEAS, Stevens Point, WI, 2009), pp. 217–220.
     
  7. P. J. Slater, Locating dominating sets and locating-dominating sets, in Proc. 7th Quad. Int. Conf. Theory and Applications of Graphs, Kalamazoo, MI, USA, June 1–5, 1992, Vol. 2 (Wiley, New York, 1995), pp. 1073–1079.
     
  8. M. Gentner, M. Henning, and D. Rautenbach, Largest domination number and smallest independence number of forests with given degree sequence, Discrete Appl. Math. 206, 181–187 (2016).
     
  9. M. Gentner, M. Henning, and D. Rautenbach, Smallest domination number and largest independence number of graphs and forests with given degree sequence, J. Graph Theory 88 (1), 131–145 (2018).
     
  10. A. D. Kurnosov, The set of all values of the domination number in trees with a given degree sequence, Diskretn. Anal. Issled. Oper. 27 (1), 61–87 (2020) [Russian] [J. Appl. Ind. Math. 14 (1), 131–147 (2020)].
     
  11. A. D. Kurnosov, On a lower bound of connected domination number for graphs with prescribed degree sequence, Tr. MFTI 12 (2), 40–54 (2020) [Russian].
     
  12. E. DeLavina, C. E. Larson, R. Pepper, B. Waller, and O. Favaron, On total domination and support vertices of a tree, AKCE Int. J. Graphs Comb. 7 (1), 85–95 (2010).
     
  13. W. J. Desormeaux, T. W. Haynes, and M. A. Henning, Improved bounds on the domination number of a tree, Discrete Appl. Math. 177, 88–94 (2014).
     
  14. V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, and R. I. Tyshkevich, Lectures on Graph Theory (Nauka, Moscow, 1990 [Russian]; B. I. Wissenschaftsverlag, Mannheim, 1994).