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

An, D. N. (2008). Some problems about Hamiltonian cycle in special graphs (In The 2nd International Conference on Theories and Applications of Computer Science (ICTACS’09)). Journal of Science and Technology, Vietnam Academy of Science and Technology, 6(5A-Special issue), 57–66.

An, D. N. (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

An, D. N. (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)

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

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)