Contractible Hamiltonian cycles in polyhedral maps

DOI10.1142/S1793830912500589MaRDI QIDQ4903644zbMATH OpenOpenAlexFDO

Authors Dipendu Maity, Ashish Kumar Upadhyay

Publication date 24 January 2013

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.4150

zbMATH Keywords

contractible Hamiltonian cyclesequivelar mapsproper trees in maps

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Abstract: We present a necessary and sufficient condition for existence of a contractible Hamiltonian Cycle in the edge graph of equivelar maps on surfaces. We also present an algorithm to construct such cycles. This is further generalized and shown to hold for more general maps.

Recommendations

• Hamiltonian cycles in polyhedral maps
• Contractible Hamiltonian cycles in triangulated surfaces
• Maximum number of contractible edges on Hamiltonian cycles of a 3-connected graph
• Hamiltonian cycles existed in plan of polyhedron
• Finding shortest contractible and shortest separating cycles in embedded graphs

Cites work

• Abstract Regular Polytopes
• Construction and enumeration of regular maps on the torus
• Diagonal flips in Hamiltonian triangulations on the projective plane
• Graph minors and graphs on surfaces
• Hamiltonian circuits in some maps on the torus
• Polytopes, graphs, and complexes

Cited in

(2)

• Hamiltonian cycles in polyhedral maps
• Contractible Hamiltonian cycles in triangulated surfaces

This page was built for publication: Contractible Hamiltonian cycles in polyhedral maps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4903644)