Hamiltonicity for convex shape Delaunay and Gabriel graphs
© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ ; We study Hamiltonicity for some of the most general variants of Delaunay and Gabriel graphs. Instead of defining these proximity graphs using circles, we use an arbitrary convex shape \(\mathcal {C}\) . Let S be a point set in the plane. The k-order Delaunay graph of S, denoted k- \({DG}_{\mathcal {C}}(S)\) , has vertex set S and edge pq provided that there exists some homothet of \(\mathcal {C}\) with p and q on its boundary and containing at most k points of S different from p and q. The k-order Gabriel graph k- \({GG}_{\mathcal {C}}(S)\) is defined analogously, except for the fact that the homothets considered are restricted to be smallest homothets of \(\mathcal {C}\) with p and q on its boundary. We provide upper bounds on the minimum value of k for which k- \({GG}_{\mathcal {C}}(S)\) is Hamiltonian. Since k- \({GG}_{\mathcal {C}}(S)\) \(\subseteq \) k- \({DG}_{\mathcal {C}}(S)\) , all results carry over to k- \({DG}_{\mathcal {C}}(S)\) . In particular, we give upper bounds of 24 for every \(\mathcal {C}\) and 15 for every point-symmetric \(\mathcal {C}\) . We also improve the bound to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular t-gons (for \(t \ge 10)\) . These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs. ; P.B. was partially supported by NSERC. P.C. was supported by CONACyT. M.S. was supported by the Czech Science Foundation, grant number GJ19-06792Y, and by institutional support RVO:67985807. R.S. was supported by MINECO through the Ram´on y Cajal program. P.C. and R.S. were also supported by projects MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1640. This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. ; Peer Reviewed ; Postprint (author's final draft)