10-Gabriel graphs are Hamiltonian

DOI10.1016/J.IPL.2015.05.013MaRDI QIDQ2353639zbMATH OpenOpenAlexFDO

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

Publication date 15 July 2015

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

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

zbMATH Keywords

computational geometryHamiltonian cyclesGabriel graphsproximity graphs

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(4)

• Matchings in higher-order Gabriel graphs
• Bottleneck matchings and Hamiltonian cycles in higher-order Gabriel graphs
• Higher-order triangular-distance Delaunay graphs: graph-theoretical properties
• Hamiltonicity for convex shape Delaunay and 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)