Research Article

Sufficient Condition and Algorithm for Hamiltonian in 3-Connected 3-Regular Planar Bipartite Graph

by  Md. Khaliluzzaman, Md. Monirul Islam, Md. Monjur Hasan
journal cover
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 117 - Issue 11
Published: May 2015
Authors: Md. Khaliluzzaman, Md. Monirul Islam, Md. Monjur Hasan
10.5120/20596-3096
PDF

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

                        @article{ 10.5120/20596-3096,
                        author  = { Md. Khaliluzzaman,Md. Monirul Islam,Md. Monjur Hasan },
                        title   = { Sufficient Condition and Algorithm for Hamiltonian in 3-Connected 3-Regular Planar Bipartite Graph },
                        journal = { International Journal of Computer Applications },
                        year    = { 2015 },
                        volume  = { 117 },
                        number  = { 11 },
                        pages   = { 6-10 },
                        doi     = { 10.5120/20596-3096 },
                        publisher = { Foundation of Computer Science (FCS), NY, USA }
                        }
                        %0 Journal Article
                        %D 2015
                        %A Md. Khaliluzzaman
                        %A Md. Monirul Islam
                        %A Md. Monjur Hasan
                        %T Sufficient Condition and Algorithm for Hamiltonian in 3-Connected 3-Regular Planar Bipartite Graph%T 
                        %J International Journal of Computer Applications
                        %V 117
                        %N 11
                        %P 6-10
                        %R 10.5120/20596-3096
                        %I Foundation of Computer Science (FCS), NY, USA
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
Computer Science
Information Sciences
No index terms available.
Keywords

Hamiltonian Cycle bipartite 3-connected 3-regular proper subset Hamiltonian path.

Powered by PhDFocusTM