Вестник КРАУНЦ. Физ.-мат. науки. 2025.Т. 53. №4. C. 9 — 28. ISSN 2079-6641

МАТЕМАТИКА
https://doi.org/10.26117/2079-6641-2025-53-4-9-28
Научная статья
Полный текст на английском языке
УДК 519.177

Содержание выпуска

Read English Version

Экстремальные топологические индексы с заданными последовательностями степеней

Ж. Хамуд^{\ast}, А. Я. Белов

Московский физико-технический институт, 141700, Институтский пер., 9, г. Долгопрудный, Россия

Аннотация. Данная статья исследует экстремальные свойства и оценки двух значимых топологических индексов в теории графов: индексов Альбертсона и Сигма, с акцентом на деревья и двудольные графы. Мы идентифицируем уникальные деревья, которые максимизируют и минимизируют индекс Альбертсона, включая звёзды и пути, и расширяем эту характеристику на двудольные графы. В этой работе мы изучаем точные верхние и нижние оценки топологических индексов для заданной последовательности степеней \mathscr{D} = (d_1, d_2, \dots , d_n). Мы выводим точные нижние и верхние оценки для индексов Альбертсона и Сигма на основе неубывающей последовательности степеней \mathscr{D} = (d_1, d_2, \dots , d_n). Установление таких оценок является фундаментальной задачей в изучении топологических индексов, поскольку эти результаты выявляют внутренние взаимосвязи различных индексов. Для генерации двудольных графов и турниров с заданными последовательностями степеней проводится анализ времени смешивания и свойств сходимости. Точные верхние и нижние оценки индекса Сигма на основе последовательностей степеней обеспечивают более глубокое понимание его поведения в деревьях. Наши результаты предлагают новые взгляды на меры структурной нерегулярности графов, подкреплённые строгими доказательствами и вычислительными алгоритмами для оценки этих индексов в случайных деревьях и лесах. Эти результаты способствуют пониманию экстремальных свойств и комбинаторных структур в теории графов с приложениями в химической теории графов и анализе сетей.

Ключевые слова: деревья, последовательность степеней, двудольный граф, топологические
индексы, экстремальность, нерегулярность.

Получение: 22.11.2025; Исправление: 01.12.2025; Принятие: 02.12.2025; Публикация онлайн: 09.12.2025

Для цитирования. Hamoud J., Belov A.Ya. Extremal topological indices with prescribed degree sequences // Вестник КРАУНЦ. Физ.-мат. науки. 2025. Т. 53. № 4. C. 9-28. EDN: ZYMYHF. https://doi.org/10.26117/2079-6641-2025-53-4-9-28.

Финансирование. Исследование было проведено без поддержки фондов

Конкурирующие интересы. Конфликтов интересов в отношении авторства и публикации нет.

Авторский вклад и ответственность. Авторы участвовали в написании статьи и полностью несут
ответственность за предоставление окончательной версии статьи в печать.

^{\ast}Корреспонденция: E-mail: hamoud.math@gmail.com

Контент публикуется на условиях Creative Commons Attribution 4.0 International License

© Hamoud J., Belov A.Ya., 2025

© ИКИР ДВО РАН, 2025 (оригинал-макет, дизайн, составление)

Список литературы

1. Abdo H., Brandt S., Dimitrov D. The total irregularity of a graph, Discrete Mathematics & Theoretical Computer Science, 2014. vol. 16, no. 1, pp. 201–206.
2. Albertson M. O. The irregularity of a graph, Ars Combinatoria, 1997. vol. 46, pp. 219–225.
3. Abdo H., Dimitrov D., Gutman I. Graph irregularity and its measures, Applied Mathematics and Computation, 2019. vol. 357, pp. 317–324.
4. Cutinha J. S., D’Souza S., Nayak S.On the minimum reformulated Albertson Index of fixed-order trees and unicyclic graphs with a given maximum degree, AKCE International Journal of Graphs and Combinatorics, 2025. vol. 22, no. 2 DOI:10.1080/09728600.2025.2458263.
5. Dimitrove D., Vukićević Z. K., Popivoda G., Sedlar J., ˜Skrekovski R., Vujo˜sević S. The σ-irregularity of trees with maximum degree 5, Disc. App. Math., 2026. vol. 382, pp. 124–136.
6. Ghalavand A., Gutman I., Tavakoli M. Irregularity measure of graphs, Journal of Mathematics, 2023. vol. 2023, pp. 4891183 DOI:10.1155/2023/4891183.
7. Harary F. Graph Theory: Addison-Wesley, 1969.
8. Ghalavand A., Ashrafi A. R. Ordering of c-cyclic graphs with respect to total irregularity., Journal of Applied Mathematics and Computing, 2020. vol. 63, no. 1-2, pp. 707–715.
9. Broutin N., Marckert J. F. Asymptotics of trees with a prescribed degree sequence and applications, Random Structures & Algorithms, 2014. vol. 44, no. 3, pp. 290–316.
10. Hamoud J., Belov A.Ya., Almahalebi M., Abdullah D. Closed-Form Analysis and Extremal Bounds of Albertson and Sigma Indices in Trees with Prescribed Degree Sequences, arXiv preprint, 2025. vol. arXiv:2510.19490 arXiv:2510.19490.
11. Hamoud J., Abdullah D.Topological Indices with Degree Sequence D of Tree, Lobachevskii Journal of Mathematics, 2025. vol. 46, no. 8, pp. 4249–4264 DOI:10.1134/S1995080225606769.
12. Hamoud J., Abdullah D. Albertson index and Sigma index in trees given by degree sequences, Chebyshevskii sbornik, 2025. vol. 26, no. 3, pp. 2–11 DOI:10.22405/2226-8383-2025-26-3-2-11.
13. Chen W. K. Applied Graph Theory. Amsterdam: North-Holland, 1971.
14. Gutman I. Geometric approach to degree-based topological indices: Sombor indices, MATCH Commun. Math. Comput. Chem., 2021. vol. 86, pp. 11–16.
15. Gutman I., Togan M., Yurttas A., Cevik A. S., Cangul I. N. Inverse problem for sigma index, MATCH Commun. Math. Comput. Chem., 2018. vol. 79, no. 3, pp. 491–508.
16. Mandal Y. C., Prvanovic M. Inverse problem for Albertson irregularity index, Journal of Algebraic Engineering Mathematics, 2022. vol. 12, no. 3, pp. 1–10.
17. Molloy M., Reed B.A critical point for random graphs with a given degree sequence, Random Structures & Algorithms, 1995. vol. 6, no. 2-3, pp. 161–180.
18. Zhang X. M., Zhang X. D., Gray D., Wang H.The number of subtrees of trees with given degree sequence, Journal of Graph Theory, 2013. vol. 73, no. 3, pp. 280–295.
19. Yang, J.; Deng, H. The Extremal Sigma Index of Connected Graphs with Given Number of Pendant Vertices, Research Square, 2023 DOI:10.21203/rs.3.rs-3373372/v1.

---

Информация об авторах

---

---