Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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...

share|improve this question

2 Answers 2

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

share|improve this answer
    
Thanks for the "b-edge" keyword and the cool reference... –  draks ... Sep 3 '12 at 6:41
up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.