8
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Jukka Suomela
    Nov 15, 2010 at 20:23
  • $\begingroup$ Thanks Jukka, Why should we exclude variable-size gadgets? It is possible to build non-Hamiltonian gadget with number of nodes $\epsilon n$ $\endgroup$
    – Mohammad Al-Turkistany
    Nov 15, 2010 at 20:33
  • 1
    $\begingroup$ Did you mean to restrict your class of graphs to connected cubic planar bipartite graphs? Otherwise the best lower bound is clearly a constant. $\endgroup$
    – Warren Schudy
    Nov 16, 2010 at 0:11
  • $\begingroup$ Yes, I'm interested in non-Hamiltonian connected cubic planar bipartite graphs. $\endgroup$
    – Mohammad Al-Turkistany
    Nov 16, 2010 at 0:15
  • $\begingroup$ 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. $\endgroup$
    – Joseph Malkevitch
    Nov 17, 2010 at 22:33

2 Answers 2

Reset to default
23
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks David especially for this nice graph. Is there an infinite set of graphs with $O(\log^2 n)$ upper bound? $\endgroup$
    – Mohammad Al-Turkistany
    Nov 15, 2010 at 22:57
  • 5
    $\begingroup$ Your ability to come up with such nice examples together with great drawings continues to amaze me ;-) $\endgroup$
    – Anthony Labarre
    Nov 15, 2010 at 22:58
  • $\begingroup$ 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? $\endgroup$
    – Mohammad Al-Turkistany
    Nov 15, 2010 at 23:25
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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