UPM Institutional Repository

Packing 1-plane Hamiltonian cycles in complete geometric graphs


Trao, Hazim Michman and Ali, Niran Abbas and Chia, Gek L. and Kilicman, Adem (2019) Packing 1-plane Hamiltonian cycles in complete geometric graphs. Filomat, 33 (6). pp. 1561-1574. ISSN 2406-0933


Counting the number of Hamiltonian cycles that are contained in a geometric graph is #P-complete even if the graph is known to be planar [15]. A relaxation for problems in plane geometric graphs is to allow the geometric graphs to be 1-plane, that is, each of its edges is crossed at most once. We consider the following question: For any set P of n points in the plane, how many 1-plane Hamiltonian cycles can be packed into a complete geometric graph Kn? We investigate the problem by taking two different situations of P, namely, when P is in convex position, wheel configurations position. For points in general position we prove the lower bound of k − 1 where n = 2k + h and 0 ≤ h < 2k. In all of the situations, we investigate the constructions of the graphs obtained.

Download File

[img] Text (Abstract)

Download (71kB)

Additional Metadata

Item Type: Article
Divisions: Faculty of Science
DOI Number: https://doi.org/10.2298/FIL1906561T
Publisher: Faculty of Sciences and Mathematics, University of Nis
Keywords: Hamiltonian; Geometric; Plane
Depositing User: Ms. Nida Hidayati Ghazali
Date Deposited: 20 Jun 2021 16:25
Last Modified: 20 Jun 2021 16:25
Altmetrics: http://www.altmetric.com/details.php?domain=psasir.upm.edu.my&doi=10.2298/FIL1906561T
URI: http://psasir.upm.edu.my/id/eprint/81605
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item