zbMATH — the first resource for mathematics

Independent dominating sets and Hamiltonian cycles. (English) Zbl 1112.05077
Summary: A graph is uniquely Hamiltonian if it contains exactly one Hamiltonian cycle. In this note we prove that there are no $$r$$-regular uniquely Hamiltonian graphs when $$r > 22$$. This improves upon earlier results of C. Thomassen [J. Comb. Theory, Ser. B 72, 104–109 (1998; Zbl 0895.05038)].

MSC:
 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C45 Eulerian and Hamiltonian graphs
Full Text:
References:
 [1] Bondy, J Combin Theory Ser B 74 pp 265– (1998) [2] and , Combinatorial enumeration, Wiley-Interscience series in discrete mathematics. John Wiley & Sons, Inc., New York, 1983. [3] and , A note on independent dominating sets and second hamiltonian cycles (Personal communication). [4] and , Problems and results on 3-chromatic hypergraphs and some related questions, In: Infinite and finite sets, et al., eds., North-Holland, Amsterdam, 1975, 609–628. [5] The multiplicity of Hamiltonian circuits in a graph, In: Recent advances in graph theory, ed., Academia, Prague, 1975, 447–480. [6] Tutte, J London Math Soc 21 pp 98– (1946) [7] Thomason, Ann Discrete Math 3 pp 3– (1978) [8] Thomassen, J Combin Theory Ser B 72 pp 104– (1998)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.