Mathematics and Computational Sciences

Efficient and resilient metro rail networks through graph domination, connectivity, and coloring methods

Document Type : Original Article

Authors

Siddharthan Rajeshkanna 1
Kungumaraj Eswarasamy 2
Jenitha Ganesan 3

1 Department of mathematics, AMET university, Chennai, India

2 Department of Science and Humanities, Nehru In- stitute of Engineering and Technology, Coimbatore, India

3 Department of Mathematics, AMET University, Chennai, India

https://doi.org/10.30511/mcs.2025.2075308.1535
Abstract
The utilization of the Indian rail system has grown at a very high rate and there is one of the largest train track networks in the world in the country. Despite the creation of various sophisticated means of transport, congestion, inefficiency and bad connectivity remain factors to contend with. To overcome these challenges, the metro rail has been
discovered to be the most possible urban mass transit system and can be easily modeled using graph theory with vertices represented by stations and edges by tracks. In this paper, we begin by examining traditional metrics like connectivity, complexity, diameter,
average distance between the terminals and potential expansion of the network in the hope
of quantifying passenger convenience and efficiency. We also advance the research with
new concepts: vertex and edge domination are used to compute the minimum critical
station for effective surveillance, vertex and edge connectivity to quantify survivability against failure and labeling or coloring techniques for use with scheduling, traffic control and resource allocation. This joint approach results in both classical and new findings for more resilient metro network planning and construction.

Keywords

Graph Theory
Metro Networks
Domination Theory
Network Resilience
Urban Transportation

Subjects

[1] Barman, K. J., & Mishra, A. (2024). Analysis of metro network by applying graph theoretical notions.
[2] Begum, F. (2024). Colorability, chromatic number and its applications on graph theory. Anusandhanvallari, 1917–1930. 
[3] Biedl, T., Bose, P., & Murali, K. (2024). A parameterized algorithm for vertex and edge connectivity of embedded graphs. In Proceedings of the 32nd Annual European Symposium on Algorithms (ESA 2024) (pp. 24–1). Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
[4] Biondini, F., Ballio, F., di Prisco, M., Bianchi, S., DAngelo, M., Zani, G., ... Ferreira, K. F. (2022). Bridge vulnerability and hazard assessment for risk-based infrastructure management. In Bridge Safety, Maintenance, Management, Life-Cycle, Resilience and Sustainability (pp. 1864–1873). CRC Press. 
[5] Conlon, D., & Lee, J. (2024). Domination inequalities and dominating graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 177(1), 167–184. 
[6] De Silva, D., Gallo, M., De Falco, L., & Nigro, E. (2023). Fire risk assessment of bridges: From state of the art to structural vulnerability mitigation. Journal of Civil Structural Health Monitoring, 13(8), 1613–1632. 
[7] Goranci, G., Henzinger, M., Nanongkai, D., Saranurak, T., Thorup, M., & Wulff-Nilsen, C. (2023). Fully dynamic exact edge connectivity in sublinear time. In Proceedings of the 2023 Annual ACM–SIAM Symposium on Discrete Algorithms (SODA) (pp.70–86). Society for Industrial and Applied Mathematics. 
[8] Jafari, H., Salehfard, S., & Aqababaei Dehkordi, D. (2024). Introducing a simple method for detecting the path between two different vertices in graphs. Mathematics and Computational Sciences, 4(4), 10–16. 
[9] Karuppiah, K., Velusamy, S., Banu, M. N., Sunantha, D., Jenitha, G., & Brindha, R. (2025). Topological data analysis (TDA) as a framework for understanding deep learning behavior. In Proceedings of the IEEE 5th International Conference on ICT in Business Industry & Government (ICTBIG) (pp. 1–7). IEEE. 
[10] Kumar, J. S., Archana, B., Muralidharan, K., & Srija, R. (2025). Spectral graph theory: Eigenvalues, Laplacians, and graphconnectivity. Metallurgical and Materials Engineering, 31(3), 78–84.
[11] Kungumaraj, E., Thivyarathi, R. C., Kenneth, C. R., Ramesh, R., Anand, M. C. J., & Naganathan, S. (2024). Efficiency enhancement in heptagonal fuzzy transportation problems. In Proceedings of the International Conference on Intelligent and Fuzzy Systems (pp. 578–585). Springer Nature Switzerland. 
[12] Kungumaraj, E., Clement Joe Anand, M., Saikia, U., Dabass, V., Ranjitha, B., & Tiwari, M. (2024). Topologized graphical method in solving fuzzy transportation problem with computational techniques. In Proceedings of the International Conference on Intelligent and Fuzzy Systems (pp. 513–521). Springer Nature Switzerland. 
[13] Meybodi, M. A., Safari, M., & Davoodijam, E. (2024). Domination-based graph neural networks. International Journal of Computers and Applications, 46(11), 998–1005.
[14] Pasham, S. D. (2023). Network topology optimization in cloud systems using advanced graph coloring algorithms. The Metascience, 1(1), 122–148.
[15] Paulraj Jayasimman, I., Jenitha, G., & Kumaravel, A. (2018). The energy graph for minimum majority domination. International Journal of Engineering & Technology, 7(4.10), 562–565. 
[16] Raza, A., & Munir, M. M. (2025). Laplacian spectra and structural insights: Applications in chemistry and network science. Frontiers in Applied Mathematics and Statistics, 11, 1519577.
Mathematics and Computational Sciences
Volume 7, Issue 1
Winter 2026
Pages 104-117

  • Receive Date 20 October 2025
  • Revise Date 29 November 2025
  • Accept Date 04 December 2025

Home

Submit Manuscript

Reviewers

Contact Us