z-logo
open-access-imgOpen Access
On uniquely Hamiltonian claw-free and triangle-free graphs
Author(s) -
Bert Seamone
Publication year - 2014
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.1784
Subject(s) - mathematics , hamiltonian path , combinatorics , hamiltonian path problem , hamiltonian (control theory) , claw , indifference graph , discrete mathematics , pancyclic graph , chordal graph , graph , 1 planar graph , mechanical engineering , engineering , mathematical optimization
A graph is uniquely Hamiltonian if it contains exactly one Hamiltonian cycle. In this note, we prove that claw-free graphs with minimum degree at least 3 are not uniquely Hamiltonian. We also show that this is best possible by exhibiting uniquely Hamiltonian claw-free graphs with minimum degree 2 and arbitrary maximum degree. Finally, we show that a construction due to Entringer and Swart can be modified to construct triangle-free uniquely Hamiltonian graphs with minimum degree 3

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom