<p>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.)</p>

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

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

<p><a href="http://dml.cz/dmlcz/129289" rel="nofollow">http://dml.cz/dmlcz/129289</a></p>

CC BY-SA 2.5
2010-11-16T19:41:36.707Z
2010-11-16T19:41:36.707Z
Joseph Malkevitch
<p>There exist cubic bipartite planar graphs in which the longest path has length only $O(\log^2 n)$:
<img src="https://i.sstatic.net/pr3wi.png" alt="alt text"></p>

CC BY-SA 2.5
2010-11-15T22:57:35.823Z
Thanks David especially for this nice graph. Is there an infinite set of graphs with $O(\log^2 n)$ upper bound?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-15T22:58:32.670Z
Your ability to come up with such nice examples together with great drawings continues to amaze me ;-)
Anthony Labarre
CC BY-SA 2.5
2010-11-15T23:25:13.723Z
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
CC BY-SA 2.5
2010-11-15T22:51:11.570Z
2010-11-15T22:51:11.570Z
David Eppstein
<p>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.</p>

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

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

CC BY-SA 2.5
2010-11-15T20:23:16.423Z
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
CC BY-SA 2.5
2010-11-15T20:33:56.757Z
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
CC BY-SA 2.5
2010-11-16T00:11:55.387Z
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
CC BY-SA 2.5
2010-11-16T00:15:26.130Z
Yes, I'm interested in non-Hamiltonian connected cubic planar bipartite graphs.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-17T22:33:56.280Z
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
CC BY-SA 2.5
2010-11-17T22:36:04.877Z
@Turkistany; A well known conjecture of David Barnette states that plane 3-valent 3-connected bipartite graphs always have hamiltonian circuits.
Joseph Malkevitch
<cc.complexity-theory><graph-theory>
Upper bounds on the length of longest simple path in non-Hamiltonian graph?
Mohammad Al-Turkistany
# Upper bounds on the length of longest simple path in non-Hamiltonian graph?

(Asked by: username_0 on 2010-11-15)

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.

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_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$?  
> **username_0**: Thanks Jukka, Why should we exclude variable-size gadgets? It is possible to build non-Hamiltonian gadget with number of nodes $\epsilon n$  
> **username_2**: Did you mean to restrict your class of graphs to _connected_ cubic planar bipartite graphs? Otherwise the best lower bound is clearly a constant.  
> **username_0**: Yes, I'm interested in non-Hamiltonian connected cubic planar bipartite graphs.  
> **username_3**: 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.  
> **username_3**: @Turkistany; A well known conjecture of David Barnette states that plane 3-valent 3-connected bipartite graphs always have hamiltonian circuits.  

---

## 2 answers

### Answer by username_4 on 2010-11-15. Score: 23 | Accepted answer

There exist cubic bipartite planar graphs in which the longest path has length only $O(\log^2 n)$:
![alt text](https://i.sstatic.net/pr3wi.png)

> **Comments:**
> **username_0**: Thanks David especially for this nice graph. Is there an infinite set of graphs with $O(\log^2 n)$ upper bound?  
> **username_5**: Your ability to come up with such nice examples together with great drawings continues to amaze me ;-)  
> **username_0**: 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?  

---

### Answer by username_3 on 2010-11-16. Score: 2

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>


---

