CONDITIONS FOR GRAPHS ON n VERTICES WITH THE SUM OF DEGREES OF ANY TWO NONADJACENT VERTICES EQUAL TO n-2 TO BE A HAMILTONIAN GRAPH
DOI:
https://doi.org/10.37569/DalatUniversity.14.3.1036(2024)Keywords:
Connected graph, Hamiltonian graph, Independent set, Regular graph, t-tough graph.Abstract
Let G be an undirected simple graph on \(n \geq 3\) vertices with the degree sum of any two nonadjacent vertices in G equal to \(n - 2\). We determine the condition for G to be a Hamiltonian graph.
Downloads
References
Bondy, J. A., & Chvátal, V. (1976). A method in graph theory. Discrete Mathematics, 15(2), 111–135. https://doi.org/10.1016/0012-365X(76)90078-9
Dirac, G. A. (1952). Some theorems on abstract graphs. Proceedings of the London Mathematical Society, s3-2(1), 69–81. https://doi.org/10.1112/plms/s3-2.1.69
Do, N. A. (2008). Some problems about Hamiltonian cycle in special graphs. Vietnam Journal of Science and Technology, 6(5A-Special issue), 57–66.
Do, N. A. (2019). Recognizing the Hamiltonian graph on n vertices with is an easy problem. International Journal of Advanced Research in Computer Science, 10(2), 42–45. https://doi.org/10.26483/ijarcs.v10i2.6403
Do, N. A. (2021). The structure of graphs on n vertices with the degree sum of any two nonadjacent vertices equal to . Dalat University Journal of Science, 11(4), 55–62. https://doi.org/10.37569/DalatUniversity.11.4.830(2021)
Erdös, P., & Hobbs, A. M. (1978). A class of Hamiltonian regular graphs. Journal of Graph Theory, 2(2), 129–135. https://doi.org/10.1002/jgt.3190020205
Graham, R. L., Grötschel, M., & Lovász, L. (Eds.). (1995). Handbook of combinatorics (Vol. 1). Elsevier.
Jung, H. A. (1978). On maximal circuits in finite graphs. Annals of Discrete Mathematics, 3, 129–144. https://doi.org/10.1016/S0167-5060(08)70503-X
Nash, C. S., & Williams, J. A. (1971). Handbook of combinatorics (Vol.1). Elsevier.
Ore, Ø. (1960). Note on Hamilton circuits. American Mathematical Monthly, 67(1), 55. https://doi.org/10.2307/2308928
Downloads
Published
Volume and Issues
Section
Copyright & License
Copyright (c) 2024 Do Nhu An, Nguyen Quang Tuan

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.