Hamiltonicity conditions in random graph models
*S. GayathriCorresponding authorgayathri@avit.ac.inDepartment of Humanities and Sciences (Mathematics Division)Aarupadai Veedu Institute of TechnologyVinayaka Mission’s Research Foundation (Deemed to be University)Paiyanoor, Chennai, Tamil Nadu, 603104, IndiaView full profile → , Latika Rahul Desailatikadesai@gmail.comDepartment of Information TechnologyAkurdiD. Y. Patil College of EngineeringAkurdi, Pune, Maharashtra, 411044, IndiaView full profile → , Bodireddy Vamalathabodireddyvamalathaaa@proton.meCentre for Multidisciplinary ResearchAnurag UniversityHyderabad, Telangana, 500088, IndiaView full profile → , Himanshu Sharmahimanshu.sharma@gla.ac.inDepartment of Computer Engineering & ApplicationsGLA UniversityMathura, Uttar Pradesh, 281406, IndiaView full profile → , Manjula Devarakonda Venkatamdvenkata@outlook.comDepartment of Computer Science & EngineeringPragati Engineering CollegeSurampalem, Kakinada District, Andhra Pradesh, 533437, IndiaView full profile → , Megha Jaggamegha.jagga.orp@chitkara.edu.inCentre of Research Impact and OutcomeChitkara UniversityRajpura, Punjab, 140417, IndiaView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 Apr 2026
- Published Online:
- 31 Oct 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JDMSC-3024
- Pages:
- 3973–3983
Abstract
Hamiltonicity of random graphs Probabilistic combinatorics: Hamiltonicity is a focal point of probabilistic combinatorics, the cross-relationship between structural graph phenomena and threshold phenomena. In this paper, the authors examine the appearance of Hamilton cycles in classical random graph models, especially, ErdosRenyi random graph G(n,p) and G(n,m). We consider probabilistic scenarios in which Hamiltonicity is a high probability phenomenon, focusing on sharp thresholding as the edge probability p is changed. The paper combines the theoretical limits with algorithmic methods of finding Hamiltonian cycles, such as randomized and greedy heuristics. The performance analysis is performed in different p regimes and transition periods between disconnected to Hamiltonian graphs are observed. Findings show that Hamiltonicity appears around p = (logn)/n, which agrees with the classical findings. Findings give the insights into the structural changes and algorithm feasibility, which can be used in theoretical knowledge and practical use in network design and reliability analysis.
Keywords
Subject Classifications
References
[1] L. E. Adame, L. M. Rivera, and A. L. Trujillo-Negrete, “Hamiltonicity of token graphs of some join graphs,” Symmetry, vol. 13, no. 6, Art. no. 1076 (2021), doi: 10.3390/sym13061076.
[2] Y. Lv, C.-K. Lin, and L. You, “A novel conditional connectivity and Hamiltonian connectivity of BCube with various faulty elements,” Mathematics, vol. 11, no. 15, Art. no. 3404 (2023), doi: 10.3390/math11153404.
[3] S. Lv and L. Zhao, “Hamiltonian indices of three classes of graphs obtained from Petersen graph,” Axioms, vol. 12, no. 6, Art. no. 580 (2023), doi: 10.3390/axioms12060580.
[4] M. Ceballos and M. Millán, “Vertex coloring and Eulerian and Hamiltonian paths of Delaunay graphs associated with sensor networks,” Mathematics, vol. 13, no. 1, Art. no. 55 (2025), doi: 10.3390/math13010055.
[5] C.-P. Chu and J. S.-T. Juan, “Weakly dimension-balanced Hamiltonian cycle on three-dimensional toroidal mesh graph,” Engineering Proceedings, vol. 120, no. 1, Art. no. 36 (2025), doi: 10.3390/engproc2025120036.
[6] Y. Shang, “Isoperimetric numbers of randomly perturbed intersection graphs,” Symmetry, vol. 11, no. 4, Art. no. 452 (2019), doi: 10.3390/sym11040452.
[7] B. Melnikov and B. Liu, “Special generation of random graphs and statistical study of some of their invariants,” Mathematics, vol. 13, no. 12, Art. no. 1904 (2025), doi: 10.3390/math13121904.
[8] Y. Y.-C. Chang and J. S.-T. Juan, “The one-fault directed dimension-balanced Hamiltonian problem in directed toroidal mesh graphs,” Applied Sciences, vol. 15, no. 24, Art. no. 13166 (2025), doi: 10.3390/app152413166.
[9] S. N. Ajani, P. Khobragade, P. V. Jadhav, R. A. Mahajan, B. Ganguly, and N. Parati, “Frontiers of computing-evolutionary trends and cutting-edge technologies in computer science and next generation application,” Journal of Electrical Systems, vol. 20, no. 1s, pp. 28–45 (2024).
[10] R. K. Gupta and A. P. Mazumdar, “A mathematical congestion-aware Dijkstra optimization model for adaptive routing in CCDN,” Journal of Information and Optimization Sciences, vol. 47, no. 4, pp. 1591–1601 (2026), doi: 10.47974/JIOS-2243.
[11] K.-J. Pai, “Constructing two edge-disjoint Hamiltonian cycles in BCube data center networks for all-to-all broadcasting,” Mathematics, vol. 14, no. 2, Art. no. 232 (2026), doi: 10.3390/math14020232.
[12] R. Maungchang, C. Detphumi, T. Khachorncharoenkul, and T. Suksumran, “Hamiltonian cycles in Cayley graphs of gyrogroups,” Mathematics, vol. 10, no. 8, Art. no. 1251 (2022), doi: 10.3390/math10080551.
[13] R. C. Poonia, T. Singh, C. Rajashri, D. Mondal, and S. M. Patil, “Optimizing communication system security through comprehensive testing and intelligent network configurations,” Journal of Information and Optimization Sciences, vol. 47, no. 5-A, pp. 1709–1717 (2026), doi: 10.47974/JIOS-2261.
[14] M. Lin, J. Wang, Q. Feng, and B. Fu, “Randomized parameterized algorithms for the kidney exchange problem,” Algorithms, vol. 12, no. 2, Art. no. 50 (2019), doi: 10.3390/a12020050.
[15] P. Prabu, M. Alsulami, D. Alsadie, A. K. J. Saudagar, M. Alkhathami, and R. C. Poonia, “Utilizing behavioral deep learning models to monitor and alert physicians regarding trauma cases,” Journal of Information and Optimization Sciences, vol. 44, no. 5, pp. 983–995 (2023), doi: 10.47974/JIOS-1461.
[16] C. Yuan, C. Zou, J. Wu, H. Feng, and J. Li, “IFDA: Intermittent fault diagnosis algorithm for augmented cubes under the PMC model,” Applied Sciences, vol. 15, no. 15, Art. no. 8197 (2025), doi: 10.3390/app15158197.
