CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
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
journal cover thumbnail

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.

Powered by PhDFocusTM