7
$\begingroup$

I would like to ask, if anybody knows, whether there exists a 3-regular bridgeless graph which does not have a hamiltonian path (not necessarily extended to a hamiltonian circuit). Thank you

$\endgroup$
  • $\begingroup$ @Hsien-Chih Chang 張顯之, yes I made mistake. $\endgroup$ – Saeed Jan 10 '11 at 8:46
  • $\begingroup$ @Saeed: That's OK, maybe later you'll find a construction with fewer nodes than the one in the paper shown by @Gautam :) $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 10 '11 at 8:49
9
$\begingroup$

See this answer to an earlier question for a bridgeless cubic graph in which the longest path is only polylogarithmically long.

$\endgroup$
3
$\begingroup$

I believe there are as shown in this article, though it seems non-trivial to discover one.

$\endgroup$
  • $\begingroup$ Thank you very much for your reply Hoonose. However, I did not express my question very well: When I refer to hamiltonian paths, I am referring to at least one simple path of |V| vertices between some pair of vertices of the graph, not necessarily between each pair of nodes. So, there may exist nodes not connected with a simple path of length |V|. For example in figure 3 of your reference, there exists a simple path that connects a pair of nodes, but not each pair of nodes. You are actually referring to "hamiltonian connected" graphs. $\endgroup$ – N27 Jan 8 '11 at 23:06
  • $\begingroup$ So let me please rephrase it: Is there a cubic bridgeless graph which does not have a simple path of |V| nodes? Even complex big graphs serving as counterexamples to relevant conjectures, such as the Grinberg (|V|=42) and Horton (|V|=96) have at least one such path $\endgroup$ – N27 Jan 8 '11 at 23:15
  • 2
    $\begingroup$ The first section of the document I linked to talks about a "Small cubic 3-connected planar graph that is not traceable", where a graph if traceable if it has a Hamiltonian path. So the first graph they show there is cubic, doesn't have any bridges, is connected, but has no Hamiltonian path. I believe this is what you desire. The second part, homogeneously traceable, refers to a Hamiltonian path between every pair, and is probably not what you are looking for. $\endgroup$ – Gautam Kamath Jan 9 '11 at 0:32
3
$\begingroup$

How about this one?


(source: yaroslavvb.com)

Update: Here are some if you restrict attention to connected 3-regular bridgeless graphs, from Mathematica's GraphData database


(source: yaroslavvb.com)

graphs = GraphData[{"Cubic", "Connected", "Bridgeless"}];
noham = Select[graphs, GraphData[#, "HamiltonianPathCount"] == 0 &]

Another update Looks like HamiltonianPathCount=0 doesn't always mean there's no Hamiltonian path, following Hamiltonian paths can be easily found


(source: yaroslavvb.com)

For the other two graphs, I didn't find any counter-examples with 1000 random greedy searches.

$\endgroup$
  • 2
    $\begingroup$ That is not even connected. Its two K_{4}'s $\endgroup$ – N27 Jan 9 '11 at 0:12
  • $\begingroup$ But it is bridgeless (obviously not what you were looking for though). $\endgroup$ – Andrew D. King Jan 9 '11 at 0:58
  • 1
    $\begingroup$ DoubleStarSnark and TuttesGraph have simple paths of length |V|. ZamfirescuGraph36 does not seem to have (I tried it 2-3 times). I needed only one counterexample so I did not try Szekeres. Thank you very much $\endgroup$ – N27 Jan 9 '11 at 2:00
  • $\begingroup$ By the way does anybody know why mathworld has "Hamiltonian path count ?" in Zamfirescu graphs? It should have 0 I guess (mathworld.wolfram.com/ZamfirescuGraphs.html) $\endgroup$ – N27 Jan 9 '11 at 2:04
  • 3
    $\begingroup$ Presumably nobody bothered to count the Hamiltonian paths in the Zamfirescu graphs. I don't know whether anybody has bothered to point out that Hamiltonian 3-regular graphs are automatically 3-edge colorable, so snarks are a good place to look for 3-regular graphs without Hamiltonian paths. $\endgroup$ – Peter Shor Jan 9 '11 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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