CFP last date
21 October 2024
Reseach Article

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

by Md. Khaliluzzaman, Md. Monirul Islam, Md. Monjur Hasan
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

@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 },
issue_date = { May 2015 },
volume = { 117 },
number = { 11 },
month = { May },
year = { 2015 },
issn = { 0975-8887 },
pages = { 6-10 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume117/number11/20596-3096/ },
doi = { 10.5120/20596-3096 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:59:04.836803+05:30
%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
%J International Journal of Computer Applications
%@ 0975-8887
%V 117
%N 11
%P 6-10
%D 2015
%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
  1. 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.
  2. 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.
  3. 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.
  4. G. A. Dirac, Some Theorems on Abstract Graphs, Proc. Lond. Math. Soc. 2 (1952), pp 69-81.
  5. P. ErdBs and A. M. Hobbs, Hamilton cycles in regular graphs of moderate degree, J. Combin. Theory Ser. B 23 (1977) 139-142.
  6. 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.
  7. G. A. Dirac, Some theorems on abstract graphs. Proc. London Math. Sot. , Ser. 3, 2 (1952) 69-81.
  8. L. Gordon, Hamiltonian circuits in graphs with many edges. Unpublished report, Sydney University, Australia.
  9. 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.
  10. D. Barnette, Conjecture 5, Recent Progress in Combinatorics, Academic Press, New York, (1969), 343.
  11. C. Thomassen, A Theorem on Paths in Planar Graphs, J. Graph Theory, 7 (1983), 169-176.
  12. Graph Theory with Application in chapter-4. J. A. Bondyan.
  13. L. de la Torre, Investigations of Barnette's Graphs, Undergraduate Thesis, Dept. of Math. , Univ. of California, Davis, 2005.
  14. G. Chartrand, "Introduction of Graph Theory", New York :Dover, 1985 pp. 29.
Index Terms

Computer Science
Information Sciences

Keywords

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