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

Authors

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

Download data is not yet available.

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

05-02-2024

Volume and Issues

Section

Natural Sciences and Technology

How to Cite

Do, N. A., & Nguyen, Q. T. (2024). 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. Dalat University Journal of Science, 14(3), 3-11. https://doi.org/10.37569/DalatUniversity.14.3.1036(2024)