Prev: When your math is wrong
Next: expanding the history chapter of this book Chapt 2 #156; ATOM TOTALITY
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.
 |  Next  |  Last
Pages: 1 2 3 4
Prev: When your math is wrong
Next: expanding the history chapter of this book Chapt 2 #156; ATOM TOTALITY