3
$\begingroup$

I'm looking for the smallest simple planar cubic hamiltonian graph without triangles and with at least one edge that never lies on a hamiltonian cycle.

I've got one with triangles $\phantom{somespaceneed}$ or one non planar example enter image description here

It's obvious that the middle edge never lies on a Hamilton cycle, since If once you start down the [middle] dark path, forever will it dominate your destiny and you will never return to the origin without crossing one vertex twice. I'm not sure, if this approach (patching 2 blobs left and right of the non-HC edge) leads to the smallest solution.

May the Force be with you...

2 Answers 2

2

From here: http://cs.anu.edu.au/~bdm/papers/PlanarCyclable19.pdf

A b-edge is an edge which is on no hamiltonian cycle in a graph. Figure [B] shows the unique smallest 3-connected cubic planar graph which has a 6-edge (both (0,3) and (4,7) are b-edges)

Figure 1.2

3

The following information may be useful in finding out what is known. I believe it was J. Bosak who first looked somewhat systematically at the question of when a graph which is planar, 3-valent and 3-connected has hamiltonian cirucits which used every edge or no edge of a graph. Edges on every HC were (not very usefully) referred to as a-edges and edges on no HC were called b-edges.

A discussion of a and b edges can be found here as well as the reference to Bosak's paper, Hamiltonian lines in cubic graphs.

https://cs.anu.edu.au/~bdm/papers/c4cp.pdf

  • 0
    Thanks $f$or the "b-edge" keyword and the cool re$f$erence...2012-09-03