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: 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? |