10-Gabriel graphs are Hamiltonian

DOI10.1016/J.IPL.2015.05.013zbMATH Open1332.05082arXiv1410.0309OpenAlexW1837675489MaRDI QIDQ2353639FDOQ2353639

Authors: Tomáš Kaiser, Maria Saumell, Nico Van Cleemput 

Publication date: 15 July 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: Given a set $S$ of points in the plane, the $k$-Gabriel graph of $S$ is the geometric graph with vertex set $S$, where $p_i,p_{j}inS$ are connected by an edge if and only if the closed disk having segment $$ as diameter contains at most $k$ points of $Ssetminus{p}_i,p_j$. We consider the following question: What is the minimum value of $k$ such that the $k$-Gabriel graph of every point set $S$ contains a Hamiltonian cycle? For this value, we give an upper bound of 10 and a lower bound of 2. The best previously known values were 15 and 1, respectively.

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

Recommendations

• 10-tough chordal graphs are Hamiltonian
• 10-tough chordal graphs are Hamiltonian (extended abstract)
• Hamilton paths in vertex-transitive graphs of order \(10p\)
• On Hamilton cycles in cubic \((10,n)\)-metacirculant graphs
• Hamilton cycles in tensor product of graphs
• scientific article; zbMATH DE number 3853123
• Every 3-connected essentially 10-connected line graph is Hamilton-connected
• Hamiltonian graphs from Kirkman to König
• Hamiltonian-connected graphs

zbMATH Keywords

computational geometryHamiltonian cyclesGabriel graphsproximity graphs

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Connectivity (05C40)

Cites Work

• The relative neighbourhood graph of a finite planar set
• Voronoi diagrams and Delaunay triangulations
• Delaunay graphs are almost as good as complete graphs
• Title not available (Why is that?)
• On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
• On structural and graph theoretic properties of higher order Delaunay graphs
• Matching points with squares
• The densest packing of 12 congruent circles in a circle
• On the expected maximum degree of Gabriel and Yao graphs
• A non-Hamiltonian, nondegenerate Delaunay triangulation
• Solving the Euclidean bottleneck matching problem by \(k\)-relative neighborhood graphs
• 20‐relative neighborhood graphs are hamiltonian
• Proximity graphs: {\(E, \delta\)}, {\(\Delta\)}, {\(\chi\)} and {\(\omega\)}

Cited In (4)

• Matchings in higher-order Gabriel graphs
• Hamiltonicity for convex shape Delaunay and Gabriel graphs
• Higher-order triangular-distance Delaunay graphs: graph-theoretical properties
• Bottleneck matchings and Hamiltonian cycles in higher-order Gabriel graphs

This page was built for publication: 10-Gabriel graphs are Hamiltonian

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