Name
Abstract | ||
|---|---|---|
We prove that the 10-Gabriel graph of any set of points is Hamiltonian.We discuss a possible way to further improve upon the previous result.We show that there exist sets of points whose 1-Gabriel graph is not Hamiltonian. 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 ¿ S are connected by an edge if and only if the closed disk having segment p i p j ¿ as diameter contains at most k points of S ¿ { 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.ipl.2015.05.013 | Information Processing Letters |
Keywords | Field | DocType |
computational geometry | Discrete mathematics,Block graph,Combinatorics,Line graph,Forbidden graph characterization,Distance-hereditary graph,Symmetric graph,Universal graph,Pancyclic graph,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
abs/1410.0309 | 11 | 0020-0190 |
Citations | PageRank | References |
3 | 0.42 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tomáš Kaiser | 1 | 225 | 31.43 |
| Maria Saumell | 2 | 11 | 2.22 |
| Nico Van Cleemput | 3 | 16 | 6.31 |