Publication: The hamiltonian number of cubic graphs
1
0
Issued Date
2008
Resource Type
File Type
application/pdf
ISSN
3029743
Other identifier(s)
2-s2.0-70349929486
Rights Holder(s)
Scopus
Bibliographic Citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol 4535 LNCS, No. (2008), p.213-223
Suggested Citation
Thaithae S., Punnim N. The hamiltonian number of cubic graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol 4535 LNCS, No. (2008), p.213-223. doi:10.1007/978-3-540-89550-3_23 Retrieved from: https://hdl.handle.net/20.500.14740/4162
Author(s)
Abstract
A Hamiltonian walk in a connected graph G of order n is a closed spanning walk of minimum length in G. The Hamiltonian number h(G) of a connected graph G is the length of a Hamiltonian walk in G. Thus h may be considered as a measure of how far a given graph is from being Hamiltonian. We prove that if G runs over the set of connected cubic graphs of order n and n ≠ 14then the values h(G) completely cover a line segment [a,b] of positive integers. For an even integer n ≥ 4, let C(3n) be the set of all connected cubic graphs of order n. We define min(h,3n = min{h(G): G ∈ C(3n)} and max(h, 3n = max{h(G):G ∈ C(3n)}. Thus for an even integer n ≥ 4, the two invariants min (h, 3n ) and max (h,3 n ) naturally arise. Evidently, min (h, 3n ) = n. The exact values of max (h, 3n ) are obtained in all situations. © 2008 Springer Berlin Heidelberg.