.svg){kind=logo}
EXTREMAL PROBLEMS IN GRAPH THEORY: A COMBINATORIAL OPTIMIZATION PERSPECTIVE
Keywords:
extremal graph theory, combinatorial optimization, Turán’s theorem, integer programming, edge density, graph invariants, NP-hard, Erdős-Stone theorem, graph algorithms, optimization boundsDOI:
https://doi.org/10.17654/0974165826001Abstract
The extremal theory of graphs considers the study of how large or small a graph invariant may be, according to certain constraints. The field crosses the overlying with combinatorial optimization, in which optimal configurations are studied under discrete conditions. Paper discusses the extremal problems in the idiom of optimization theory, where analytically driven approaches and computational methods are introduced, that complement the insights on how graph structures tend to act under the extremal conditions. We discuss some classical results like Turán type theorems, Mantel theorems and the Erdős Stone theorems and state their formulations in optimization terms. With integer programming and greedy algorithms, we find solutions to some extremal problems and compute their complexity and compare theoretical predictions and experimental results. This was done in our research, proving the possibility that optimization strategies be incorporated into the extremal graph theory and a foundation towards the further development of the algorithm in the subject.
Received: July 10, 2025
Revised: July 28, 2025
Accepted: August 11, 2025
References
[1] K. T. Chung, C. K. M. Lee and Y. P. Tsang, Neural combinatorial optimization with reinforcement learning in industrial engineering: a survey, Artificial Intelligence Review 58(5) (2025). doi: 10.1007/s10462-024-11045-1.
[2] F. Peres and M. Castelli, Combinatorial optimization problems and metaheuristics: review, challenges, design, and development, Applied Sciences 11(14) (2021), 6449. doi: 10.3390/app11146449.
[3] L. Ding, C. Li, D. Jin and S. Ding, Survey of spectral clustering based on graph theory, Pattern Recognition 151 (2024), 110366.
doi: 10.1016/j.patcog.2024.110366.
[4] S. Kumar and E. Munapo, Innovative ways of developing and using specific purpose alternatives for solving hard combinatorial network routing and ordered optimisation problems, Appl. Math. 4(2) (2024), 791-805.
doi: 10.3390/appliedmath4020042.
[5] J. Falla, Q. Langfitt, Y. Alexeev and I. Safro, Graph representation learning for parameter transferability in quantum approximate optimization algorithm, Quantum Machine Intelligence 6(2) (2024). doi: 10.1007/s42484-024-00178-9.
[6] C. Squires and C. Uhler, Causal structure learning: a combinatorial perspective, Foundations of Computational Mathematics 23(5) (2022), 1781-1815.
doi: 10.1007/s10208-022-09581-9.
[7] R. Zhang, J. Wang, C. Liu, K. Su, H. Ishibuchi and Y. Jin, Synergistic integration of metaheuristics and machine learning: latest advances and emerging trends, Artificial Intelligence Review 58(9) (2025). doi: 10.1007/s10462-025-11266-y.
[8] B. Chen, L. Cao, C. Chen, Y. Chen and Y. Yue, A comprehensive survey on the chicken swarm optimization algorithm and its applications: state-of-the-art and research challenges, Artificial Intelligence Review 57(7) (2024).
doi: 10.1007/s10462-024-10786-3.
[9] K. Smith-Miles, Understanding instance hardness for optimisation algorithms: methodologies, open challenges and post-quantum implications, Applied Mathematical Modelling 142 (2025), 115965. doi: 10.1016/j.apm.2025.115965.
[10] Licheng Jiao, Xue Song, Chao You, Xu Liu, Lingling Li, Puhua Chen, Xu Tang, Zhixi Feng, Fang Liu, Yuwei Guo, Shuyuan Yang, Yangyang Li, Xiangrong Zhang, Wenping Ma, Shuang Wang, Jing Bai and Biao Hou, AI meets physics: a comprehensive survey, Artificial Intelligence Review 57(9) (2024).
doi: 10.1007/s10462-024-10874-4.
[11] W. Jiang, H. Han, Y. Zhang, J. Wang, M. He, W. Gu, J. Mu and X. Cheng, Graph neural networks for routing optimization: challenges and opportunities, Sustainability 16(21) (2024), 9239. https://doi.org/10.3390/su16219239.
[12] V. Tomar, M. Bansal and P. Singh, Metaheuristic algorithms for optimization: a brief review, Engineering Proceedings (2024), 238.
doi: 10.3390/engproc2023059238.
[13] R. Abdulkadirov, P. Lyakhov and N. Nagornov, Survey of optimization algorithms in modern neural networks, Mathematics 11(11) (2023), 2466.
doi: 10.3390/math11112466.
[14] W. Jiang, H. Han, Y. Zhang, J. Wang, M. He, W. Gu, J. Mu and X. Cheng, Graph neural networks for routing optimization: challenges and opportunities, Sustainability 16(21) (2024), 9239. https://doi.org/10.3390/su16219239.
[15] S. Dauzère-Pérès, J. Ding, L. Shen and K. Tamssaouet, The flexible job shop scheduling problem: a review, European Journal of Operational Research 314(2) (2023), 409-432. doi: 10.1016/j.ejor.2023.05.017.
[16] Konstantinos F. Kantelis, Vassilios Asteriou, Aliki Papadimitriou-Tsantarliotou, Anthi Petrou, Lefteris Angelis, Petros Nicopolitidis, Georgios Papadimitriou and Ioannis S. Vizirianakis, Graph theory-based simulation tools for protein structure networks, Simulation Modelling Practice and Theory 121 (2022), 102640.
doi: 10.1016/j.simpat.2022.102640.
[17] N. Markovich and M. Vaičiulis, Extreme value statistics for evolving random networks, Mathematics 11(9) (2023), 2171. doi: 10.3390/math11092171.
[18] Bo Ning, Note on mantel theorem and Turán theorem, Graph. Comb. 40 (2024). https://doi.org/10.1007/s00373-024-02832-2.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 PUSHPA PUBLISHING HOUSE, PRAYAGRAJ, INDIA
This work is licensed under a Creative Commons Attribution 4.0 International License.
_________________________
Attribution: Credit Pushpa Publishing House as the original publisher, including title and author(s) if applicable.
Contact Pushpa Publishing House for more info or permissions.
Journal Impact Factor: 
