Vestnik КRAUNC. Fiz.-Mat. Nauki. 2025. vol. 53. no. 4. P. 9 – 28. ISSN 2079-6641

MATHEMATICS
https://doi.org/10.26117/2079-6641-2025-53-4-9-28
Research Article
Full text in English
MSC: 05C05, 05C12, 05C20, 05C25, 05C35, 05C76, 68R10

Contents of this issue

Read Russian Version

Extremal Topological Indices with Prescribed Degree Sequences

J. Hamoud^{\ast}, A.Ya. Belov

Moscow Institute of Physics and Technology, Institutskii per. 9, Dolgoprudnyi, 141700 Russia

Abstract. This paper explores the extremal properties and bounds of two significant topological indices in graph theory: the Albertson and Sigma indices, with an emphasis on trees and bipartite graphs. We identify the unique trees that maximize and minimize the Albertson index, including stars and paths, and extend this characterization to bipartite graphs. In this paper, we investigate the sharp upper and lower bounds of topological indices for a given degree sequence \mathscr{D} = (d_1, d_2, \dots, d_n). We derive exact lower and upper bounds for the Albertson index and Sigma index based on a non-increasing degree sequence \mathscr{D} = (d_1, d_2, \dots, d_n). Establishing such bounds is a fundamental challenge in the study of topological indices, as these results reveal inherent relationships among various indices. For generating bipartite graphs and tournaments with prescribed degree sequences, analyzing their mixing times and convergence properties. The sharp upper and lower bounds for the Sigma index based on degree sequences, providing a deeper understanding of its behavior in trees. Our findings offer novel insights into graph irregularity measures, supported by rigorous proofs and computational algorithms for evaluating these indices in random trees and forests. These results contribute to the understanding of extremal properties and combinatorial structures in graph theory, with applications in chemical graph theory and network analysis.

Key words: Trees, Degree sequence, Bipartite graph, Topological indices, Extremal, Irregularity.

Received: 22.11.2025; Revised: 01.12.2025; Accepted: 02.12.2025; First online: 09.12.2025

For citation. Hamoud J., Belov A.Ya. Extremal topological indices with prescribed degree sequences. Vestnik KRAUNC. Fiz.-mat. nauki. 2025, 53: 4, 9-28. EDN: ZYMYHF. https://doi.org/10.26117/2079-6641-2025-53-4-9-28.

Funding. Not funding

Competing interests. There are no conflicts of interest regarding authorship and publication.

Contribution and Responsibility. All authors contributed to this article. Authors are solely responsible for providing the final version of the article in print. The final version of the manuscript was approved by all authors.

^{\ast}Correspondence: E-mail: hamoud.math@gmail.com

The content is published under the terms of the Creative Commons Attribution 4.0 International License

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

© Institute of Cosmophysical Research and Radio Wave Propagation, 2025 (original layout, design, compilation)

References

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.

---

Information about the authors

---

---