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
$\begingroup$
$\endgroup$
2
-
$\begingroup$ @Hsien-Chih Chang 張顯之, yes I made mistake. $\endgroup$– SaeedJan 10, 2011 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, 2011 at 8:49
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
See this answer to an earlier question for a bridgeless cubic graph in which the longest path is only polylogarithmically long.
answered Jan 10, 2011 at 16:57
$\begingroup$
$\endgroup$
3
I believe there are as shown in this article, though it seems non-trivial to discover one.
-
$\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$– N27Jan 8, 2011 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$– N27Jan 8, 2011 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$ Jan 9, 2011 at 0:32
$\begingroup$
$\endgroup$
5
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)
- http://mathworld.wolfram.com/DoubleStarSnark.html
- http://mathworld.wolfram.com/SzekeresSnark.html
- http://mathworld.wolfram.com/TuttesGraph.html
- http://mathworld.wolfram.com/ZamfirescuGraphs.html
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.
answered Jan 9, 2011 at 0:04
-
2
-
$\begingroup$ But it is bridgeless (obviously not what you were looking for though). $\endgroup$ Jan 9, 2011 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$– N27Jan 9, 2011 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$– N27Jan 9, 2011 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$ Jan 9, 2011 at 2:32