Prev: When your math is wrong
Next: expanding the history chapter of this book Chapt 2 #156; ATOM TOTALITY
From: bill on 18 Jun 2010 20:51
On Jun 12, 11:25 am, Yann David <yann_da...(a)hotmail.com> wrote:
> 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

There are maximal triangulations which have no
Hamiltonian paths.

Any semi-H paths that terminate on the same face are
technically H paths. Therefore in any maximal triangulation without a
Hamiltonian path; all semi-H paths will terminate on different
faces.

To create a graph without an H path, start with a
simple max triangulation. This graph can have very few vertices. I am
not sure how few, but I remember that the number is less than ten.
Add a vertex to each face and connect that vertex to the three
vertices of the face.

regards, Bill J
From: Jim Ferry on 19 Jun 2010 08:52
On Jun 18, 8:51 pm, bill <b92...(a)yahoo.com> wrote:
> On Jun 12, 11:25 am, Yann David <yann_da...(a)hotmail.com> wrote:
>
>
>
>
>
> > 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
>
> There are maximal triangulations which have no
> Hamiltonian paths.
>
> Any semi-H paths that terminate on the same face are
> technically H paths.  Therefore in any maximal triangulation without a
> Hamiltonian path; all semi-H paths will terminate on different
> faces.
>
> To create a graph without an H path, start with a
> simple max triangulation. This graph can have very few vertices. I am
> not sure how few, but I remember that the number is less than ten.
> Add a vertex to each face and connect that vertex to the three
> vertices of the face.
>
> regards, Bill J

Okay, using that idea, add a vertex to each face of an octahedron.
That makes 6 original vertices plus 8 new ones. New vertices are
adjacent only to original vertices, so a path containing 8 new
vertices contains at least 7 original ones. Michelangelo: Too many?
Pope: Well, of course it's too many!
From: bill on 19 Jun 2010 14:58
On Jun 19, 5:52 am, Jim Ferry <corkleb...(a)hotmail.com> wrote:
> On Jun 18, 8:51 pm, bill <b92...(a)yahoo.com> wrote:
>
>
>
> > On Jun 12, 11:25 am, Yann David <yann_da...(a)hotmail.com> wrote:
>
> > > 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
>
> > There are maximal triangulations which have no
> > Hamiltonian paths.
>
> > Any semi-H paths that terminate on the same face are
> > technically H paths.  Therefore in any maximal triangulation without a
> > Hamiltonian path; all semi-H paths will terminate on different
> > faces.
>
> > To create a graph without an H path, start with a
> > simple max triangulation. This graph can have very few vertices. I am
> > not sure how few, but I remember that the number is less than ten.
> > Add a vertex to each face and connect that vertex to the three
> > vertices of the face.
>
> > regards, Bill J
>
> Okay, using that idea, add a vertex to each face of an octahedron.
> That makes 6 original vertices plus 8 new ones.  New vertices are
> adjacent only to original vertices, so a path containing 8 new
> vertices contains at least 7 original ones.  Michelangelo: Too many?
> Pope: Well, of course it's too many!

Michelangelo: "Suppose I leave out one of the new
vertices?"

Pope: "Then there might be a Hamiltonian path."

Michelangelo: "No. Any semi-Hamiltonian path (if one
existed) would start and end on a new vertex. There
would be no way to complete the Hamiltonian."

Pope: "But could such a path exist?"

Michelangelo: "I don't know. Ask Jim."
From: Jim Ferry on 20 Jun 2010 11:22
On Jun 19, 2:58 pm, bill <b92...(a)yahoo.com> wrote:
> On Jun 19, 5:52 am, Jim Ferry <corkleb...(a)hotmail.com> wrote:
>
>
>
>
>
> > On Jun 18, 8:51 pm, bill <b92...(a)yahoo.com> wrote:
>
> > > On Jun 12, 11:25 am, Yann David <yann_da...(a)hotmail.com> wrote:
>
> > > > 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
>
> > > There are maximal triangulations which have no
> > > Hamiltonian paths.
>
> > > Any semi-H paths that terminate on the same face are
> > > technically H paths.  Therefore in any maximal triangulation without a
> > > Hamiltonian path; all semi-H paths will terminate on different
> > > faces.
>
> > > To create a graph without an H path, start with a
> > > simple max triangulation. This graph can have very few vertices. I am
> > > not sure how few, but I remember that the number is less than ten.
> > > Add a vertex to each face and connect that vertex to the three
> > > vertices of the face.
>
> > > regards, Bill J
>
> > Okay, using that idea, add a vertex to each face of an octahedron.
> > That makes 6 original vertices plus 8 new ones.  New vertices are
> > adjacent only to original vertices, so a path containing 8 new
> > vertices contains at least 7 original ones.  Michelangelo: Too many?
> > Pope: Well, of course it's too many!
>
> Michelangelo: "Suppose I leave out one of the new
> vertices?"
>
> Pope: "Then there might be a Hamiltonian path."
>
> Michelangelo: "No. Any semi-Hamiltonian path (if one
> existed) would start and end on a new vertex. There
> would be no way to complete the Hamiltonian."
>
> Pope:  "But could such a path exist?"
>
> Michelangelo: "I don't know.  Ask Jim."

Such a path exists. My first attempt to draw one was successful, so,
unless I was unusually lucky, it would seem that anyone interested
could just write one down. Or commission an artist to do so, though
he might decide to add a kangaroo, a trampoline act, and a mariachi
band.
From: bill on 20 Jun 2010 19:28
On Jun 19, 5:52 am, Jim Ferry <corkleb...(a)hotmail.com> wrote:
> On Jun 18, 8:51 pm, bill <b92...(a)yahoo.com> wrote:
>
>
>
> > On Jun 12, 11:25 am, Yann David <yann_da...(a)hotmail.com> wrote:
>
> > > 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
>
> > There are maximal triangulations which have no
> > Hamiltonian paths.
>
> > Any semi-H paths that terminate on the same face are
> > technically H paths.  Therefore in any maximal triangulation without a
> > Hamiltonian path; all semi-H paths will terminate on different
> > faces.
>
> > To create a graph without an H path, start with a
> > simple max triangulation. This graph can have very few vertices. I am
> > not sure how few, but I remember that the number is less than ten.
> > Add a vertex to each face and connect that vertex to the three
> > vertices of the face.
>
> > regards, Bill J
>
> Okay, using that idea, add a vertex to each face of an octahedron.
> That makes 6 original vertices plus 8 new ones.  New vertices are
> adjacent only to original vertices, so a path containing 8 new
> vertices contains at least 7 original ones.  Michelangelo: Too many?
> Pope: Well, of course it's too many!

Would you agree that an octahedron with all 8 "new" vertices has no
semi-hamiltonian or full hamiltonian paths; and that an an octahedron
with only 7 "new" vertices has semi-hamiltonian paths, but no
hamiltonian paths?
First  |  Prev  |  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