A large set of non-Hamiltonian graphs

DOI10.1016/S0166-218X(01)00219-0zbMath0989.05068OpenAlexW2042599036MaRDI QIDQ5954242

Gyula Y. Katona

Publication date: 22 July 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00219-0

zbMATH Keywords

Hamiltonian cycleedge-toughness

Mathematics Subject Classification ID

Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• Recognizing tough graphs is NP-hard
• The complexity of facets (and some facets of complexity)
• Toughness and edge-toughness
• Better approximations of non-Hamiltonian graphs
• Not every 2-tough graph is Hamiltonian
• Tough graphs and Hamiltonian circuits.