Arches and galleries

Subject:	Arches and galleries
Date:	Wed, 9 Dec 2009 17:14:04 -0800 (PST)

Hello.

The following simple procedure generates graphs that seem to be
Hamiltonian, but I don't manage to prove or disprove it. Will you be
any luckier (or just plain smarter:)?

The procedure basically accumulates finitely many "arches" on a
straight line (the "base").
There's no constraint on the first arch; each subsequent arch must
have exactly one "foot" (extremal point of contact with the base)
strictly between the feet of some preceding arch.

Example:

(1st arch)

+----1---+
| |
| |
----a--------b---------

(2nd arch)

+----1---+
| |
| |
----a---c----b-----d--
| |
| |
+-----2----+

(3rd arch)

+----1---+
| |
| |
----a---c--e-b-----d--f
| | | |
| | | |
+--|--2----+ |
| |
+-----3----+

I hope you get the idea. No other ingredients seem necessary to make
it work: the feet may overlap, and I don't demand that the drawing be
planar (even though some interesting things, or just a simpler proof,
could be found for planar arch systems).

The graph under consideration is formed naturally: the feet of the
arches are the nodes; the arches and the segments of the base that
separate successive arch feet form the edges. Let's call such a graph
a "gallery".

For instance, the above drawing yields the following graph:

G = ( V = {a, b, c, d, e, f}, E = { (a, b), (c, d), (e, f), (a, c),
(c, e), (e, b), (b, d), (d, f) } )

One Hamiltonian cycle is a-b-e-f-d-c-a. (A Hamiltonian cycle is a path
that traverses each node exactly once before returning to its starting
point.)

Is that a known problem? Is any solution available? Is it difficult to
recognize that a graph is a gallery?

Any comments or suggestions are welcome!

Cheers,

Yann David