Hamiltonian cycle problem is $NP$-complete on cubic planar bipartite graphs. I'm interested in upper bounds on the length of the longest simple path in non-Hamiltonian cubic planar bipartite graphs.

What is the best known upper bound on the length of longest simple path in non-Hamiltonian cubic planar bipartite graphs?

Edit: Also, I am interested in non-trivial lower bounds on the length of the longest simple path in this class of graphs.

  • 1
    Why should there be an upper bound? Can't you take an arbitrary Hamiltonian cubic planar bipartite graph, and replace one edge by a small gadget that makes the graph non-Hamiltonian? Hence you can't have anything better than $n - C$ for a small constant $C$? – Jukka Suomela Nov 15 '10 at 20:23
  • Thanks Jukka, Why should we exclude variable-size gadgets? It is possible to build non-Hamiltonian gadget with number of nodes $\epsilon n$ – Mohammad Al-Turkistany Nov 15 '10 at 20:33
  • 1
    Did you mean to restrict your class of graphs to connected cubic planar bipartite graphs? Otherwise the best lower bound is clearly a constant. – Warren Schudy Nov 16 '10 at 0:11
  • Yes, I'm interested in non-Hamiltonian connected cubic planar bipartite graphs. – Mohammad Al-Turkistany Nov 16 '10 at 0:15
  • The graph shown is cubic, bipartite, plane, and 2-connected. It can be thought of as starting with the cubic, bipartite, plane, multigraph consisting of two vertices and three faces which are digons (2 sides). Now, one can replace edges in this graph with a copy of the graph obtained by taking a 3-dimensional cube and cutting one edge of this cube and taking the resulting "gadget" to be "inserted" in (or attached to) an edge of the original graph. Thus, the "gadgets" that you see in the graph above are "copies" of the 3-cube. One can use this "trick" to insert other graphs into an edge. – Joseph Malkevitch Nov 17 '10 at 22:33
up vote 21 down vote accepted

There exist cubic bipartite planar graphs in which the longest path has length only $O(\log^2 n)$: alt text

  • Thanks David especially for this nice graph. Is there an infinite set of graphs with $O(\log^2 n)$ upper bound? – Mohammad Al-Turkistany Nov 15 '10 at 22:57
  • 5
    Your ability to come up with such nice examples together with great drawings continues to amaze me ;-) – Anthony Labarre Nov 15 '10 at 22:58
  • As your nice example shows, It is possible to construct recursively infinite set of graphs with the given upper bound. So my question should be: Given a graph in a class with upper bound such as $O(\log^k n)$, Can we efficiently find the longest path? – Mohammad Al-Turkistany Nov 15 '10 at 23:25

Questions of this kind are especially interesting for graphs which are 3-polytopal (edge-vertex graphs of 3-dimensional convex polytopes) and for the case of the graph being bipartite. (Also for higher-dimensional polytopes.)

The concept of "shortness exponent" has emerged to measure how short a longest cycle might be in a graph which has no hamiltonian circuit and which is within a family of graphs.

This relatively recent paper lists many references but others can be found using the string: shortness exponent polytopes:

http://dml.cz/dmlcz/129289

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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