semi-Hamiltonian paths in planar triangulations
in [Theory]
|
Prev: Exchange of the "oracle machine" and the "oracle" in the polynomial-time hierachy
Next: [] semi-Hamiltonian paths in planar triangulations
From: Yann David on 12 Jun 2010 14:25 Hello. I'd like to know whether there is any known simple instance of planar triangulation (finite planar graph which is maximal in the sense that no edge can be added to it) in which there is no semi-Hamiltonian path of which both endpoints are on the external face. (A semi-Hamiltonian path is an elementary path that traverses each vertex of the graph exactly once.) One could, more specifically, ask for a triangulation in which no semi- Hamiltonian path has both endpoints on the same face (be it the outer one or otherwise) or even without any semi-Hamiltonian path at all (a non semi-Hamiltonian triangulation). Any solutions, pointers, suggestions... are most welcome! Cheers, Yann David
From: William Elliot on 13 Jun 2010 02:13 On Sat, 12 Jun 2010, Yann David wrote: > I'd like to know whether there is any known simple instance of planar > triangulation (finite planar graph which is maximal in the sense that > no edge can be added to it) in which there is no semi-Hamiltonian path > of which both endpoints are on the external face. > > (A semi-Hamiltonian path is an elementary path that traverses each > vertex of the graph exactly once.) > > One could, more specifically, ask for a triangulation in which no semi- > Hamiltonian path has both endpoints on the same face (be it the outer > one or otherwise) or even without any semi-Hamiltonian path at all (a > non semi-Hamiltonian triangulation). > o | o--o--o in monospace font, has no Hamiltonian paths. > Any solutions, pointers, suggestions... are most welcome! >
From: stdazi on 13 Jun 2010 06:08 On Jun 13, 8:13 am, William Elliot <ma...(a)rdrop.remove.com> wrote: > On Sat, 12 Jun 2010, Yann David wrote: > > I'd like to know whether there is any known simple instance of planar > > triangulation (finite planar graph which is maximal in the sense that > > no edge can be added to it) in which there is no semi-Hamiltonian path > > of which both endpoints are on the external face. > > > (A semi-Hamiltonian path is an elementary path that traverses each > > vertex of the graph exactly once.) > > > One could, more specifically, ask for a triangulation in which no semi- > > Hamiltonian path has both endpoints on the same face (be it the outer > > one or otherwise) or even without any semi-Hamiltonian path at all (a > > non semi-Hamiltonian triangulation). > > o > | > o--o--o > > in monospace font, has no Hamiltonian paths. > > > Any solutions, pointers, suggestions... are most welcome! how is that a triangulation?
From: William Elliot on 13 Jun 2010 06:21 On Sun, 13 Jun 2010, stdazi(a)gmail.com wrote: > On Jun 13, 8:13�am, William Elliot <ma...(a)rdrop.remove.com> wrote: >> On Sat, 12 Jun 2010, Yann David wrote: >>> I'd like to know whether there is any known simple instance of planar >>> triangulation (finite planar graph �which is maximal in the sense that >>> no edge can be added to it) in which there is no semi-Hamiltonian path >>> of which both endpoints are on the external face. >> >>> (A semi-Hamiltonian path is an elementary path that traverses each >>> vertex of the graph exactly once.) >> >>> One could, more specifically, ask for a triangulation in which no semi- >>> Hamiltonian path has both endpoints on the same face (be it the outer >>> one or otherwise) or even without any semi-Hamiltonian path at all (a >>> non semi-Hamiltonian triangulation). >> >> � � o >> � � | >> o--o--o >> >> in monospace font, has no Hamiltonian paths. >> >>> Any solutions, pointers, suggestions... are most welcome! > > how is that a triangulation? > It's a finite planar graph as OP described above. Why is the beginning of your sentence not capitalized?
From: stdazi on 13 Jun 2010 06:35
On Jun 13, 12:21 pm, William Elliot <ma...(a)rdrop.remove.com> wrote: > On Sun, 13 Jun 2010, std...(a)gmail.com wrote: > > On Jun 13, 8:13 am, William Elliot <ma...(a)rdrop.remove.com> wrote: > >> On Sat, 12 Jun 2010, Yann David wrote: > >>> I'd like to know whether there is any known simple instance of planar > >>> triangulation (finite planar graph which is maximal in the sense that > >>> no edge can be added to it) in which there is no semi-Hamiltonian path > >>> of which both endpoints are on the external face. > > >>> (A semi-Hamiltonian path is an elementary path that traverses each > >>> vertex of the graph exactly once.) > > >>> One could, more specifically, ask for a triangulation in which no semi- > >>> Hamiltonian path has both endpoints on the same face (be it the outer > >>> one or otherwise) or even without any semi-Hamiltonian path at all (a > >>> non semi-Hamiltonian triangulation). > > >> o > >> | > >> o--o--o > > >> in monospace font, has no Hamiltonian paths. > > >>> Any solutions, pointers, suggestions... are most welcome! > > > how is that a triangulation? > > It's a finite planar graph as OP described above. > Why is the beginning of your sentence not capitalized? as far as I can see he asked for a finite planar triangulation. the beginning of my sentences are not capitalized because i'm too lazy to do so. |