Determing a Hamiltonian cycle or not in bipartite cubic graph is polynomial
Guohun Zhu
Guilin University of Electronic Technology
No.1 Jinji Road, Guilin, 541004, China
The main theorem is shown in follow.
THEOREM 1 Given a bicubic graph G, Determining a Hamiltonian cycle exists or not is no more than O(n^3.5) time.
Determining a Hamiltonian cycle in 2connected bipartite cubic graph is a NPcompleted problem [1]. Although I had proved the Hamiltonian cycle problem on degree bound two is Polynomial [2]. Unfortunately, it is hard to reduce the cubic graph to the digraph graph with degree bound two by simple substitute the edge into two symmetric arcs, since the in out degree both are 3.
Our approach is to reduce the bipartite cubic graph into a 2factor and a perfect matching, which comes from the petersen theorem.
THEOREM 2 [4] bridgeless cubic bipartite graph has a 1factor and hence have a 2factor.
Since bipartite cubic graph G include a 2factor and a perfect matching. Then it is easy to obtain follows lemma.
Lemma 1 Given a bridgeless bipartite cubic graph G, assume the M is a perfect matching of G. then GM is a 2factor graph.
According to the principle of reverse function of Zmapping in [3]. It is easy to deduce that.
Lemma 2 Given a bridgeless bipartite cubic graph G and a perfect matching M , then the reverse function of zmapping is a digraph $D$ with degree bound two.
Thus, it is easy to deduce that
Lemma 3 if $D$ is Hamiltonian, then $G$ is Hamiltonian.
This is a sufficient condition for bipartite cubic graph. The sufficient and necessary conditions will be described soon.
I implement the idea with C++ under Linux and Windows.
Now we given the binary distribution file as following.
Linux : hcpbicubic (which had been test under slackware 10.0)
Windows: Hcpbicubic.exe (which had been test under Windows2000, Windows XP )
How to use the tool.
Firstly, it needs to write the adjacency matrix of a given graph. Then you should create a text file include the adjacency matrix as follows.
Input data format:
First line: <number of vertex>
From second line: adjacency matrix of Graph.
Test bench
Testing data We selected some famous graph, one of test data is shown very hard for many availed tools (as far as we known).
NonHamiltonian graph: Horton96.txt[5] , 50cubic.txt [6]
Hamiltonian graph: 96h.txt , 50h.txt
Reference:
[1] T. Akiyama, T. Nishizeki, N. Saito, NPCompleteness of the Hamiltonian Cycle Problem for Bipartite Graphs. Journal of Information Processing, Vol. 3 No. 2, (1980), 7376
[2] Guohun Zhu, The Complexity of HCP in Digraphs with Degree Bound Two . arXiv:0704.0309v3
[3]Guohun Zhu. The Complexity of Determining Existence a Hamiltonian Cycle is $O(n^3)$. arXiv:0706.2725
[4] J. Petersen, Die Theorie der regul?ren Graphen, Acta Math. 15 (1891), 193¨C220.
[5] Bondy, J. A. and Murty , U. S. R. Graph Theory with Applications. New York : North Holland , pp. 61 and 240, 1976.
[6] Branko GrÄunbaum. 3connected configurations (n3) with no Hamiltonian circuit. Bull. Inst. Combin. Appl., 46:1526, 2006.
