The week's pick
Reseach Article
Sufficient Condition and Algorithm for Hamiltonian in 3-Connected 3-Regular Planar Bipartite Graph
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 117 - Number 11 |
| Year of Publication: 2015 |
| Authors: Md. Khaliluzzaman, Md. Monirul Islam, Md. Monjur Hasan |
10.5120/20596-3096
|
Md. Khaliluzzaman, Md. Monirul Islam, Md. Monjur Hasan . Sufficient Condition and Algorithm for Hamiltonian in 3-Connected 3-Regular Planar Bipartite Graph. International Journal of Computer Applications. 117, 11 ( May 2015), 6-10. DOI=10.5120/20596-3096
Abstract
A graph G (V, E) is said to be Hamiltonian if it contains a spanning cycle. The spanning cycle is called a Hamiltonian cycle of G and G is said to be a Hamiltonian graph. A Hamiltonian path is a path that contains all the vertices in V (G) but does not return to the vertex in which it began. In this paper, we study Hamiltonicity of 3-connected, 3-regular planar bipartite graph G with partite sets V=M ? N. We shall prove that G has a Hamiltonian cycle if G is balanced with M = N. For that we present an algorithm for a bipartite graph KM,N where M>3, N>3 and M,N both are even to possess a Hamiltonian cycle. In particular, we also prove a theorem for S proper subset (M or N) of V the number of components W (G-S) = S implies the graph has a Hamiltonian path.
References
- M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, NY, USA, 1979.
- M. Sohel Rahman, M. Kaykobad, and Jesun Sahariar Firoz, "New Sufficient Conditions for Hamiltonian Paths," The Scientific World Journal, vol. 2014, Article ID 743431, 6 pages, 2014. doi:10. 1155/2014/743431.
- M. R. Garey and D. S. Jhonson, Computers and Intractability: A Guide to the Theory of NP Completeness, W. H. Freeman and Company, New York.
- G. A. Dirac, Some Theorems on Abstract Graphs, Proc. Lond. Math. Soc. 2 (1952), pp 69-81.
- P. ErdBs and A. M. Hobbs, Hamilton cycles in regular graphs of moderate degree, J. Combin. Theory Ser. B 23 (1977) 139-142.
- Y. -J. Zhu, Z. -H. Liu and Z. -G. Yu, 2-connected k-regular graphs on at most 3k + 3 vertices to be Hamiltonian, J. Systems Sci. Math. Sci. 6 (1) (1986) 36-49 and (2) 1986) 136-145.
- G. A. Dirac, Some theorems on abstract graphs. Proc. London Math. Sot. , Ser. 3, 2 (1952) 69-81.
- L. Gordon, Hamiltonian circuits in graphs with many edges. Unpublished report, Sydney University, Australia.
- D. A. Holton, B. Manvel, and B. D. McKay, Hamiltonian cycles in cubic 3- connected bipartite planar graphs, 1. Comb. Th. B, 38 (3) (1985), 279-297.
- D. Barnette, Conjecture 5, Recent Progress in Combinatorics, Academic Press, New York, (1969), 343.
- C. Thomassen, A Theorem on Paths in Planar Graphs, J. Graph Theory, 7 (1983), 169-176.
- Graph Theory with Application in chapter-4. J. A. Bondyan.
- L. de la Torre, Investigations of Barnette's Graphs, Undergraduate Thesis, Dept. of Math. , Univ. of California, Davis, 2005.
- G. Chartrand, "Introduction of Graph Theory", New York :Dover, 1985 pp. 29.
Index Terms
Keywords