CFP last date
22 April 2024
Reseach Article

Particular Type of Hamiltonian Graphs and their Properties

by Kanak Chandra Bora, Bichitra Kalita
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 96 - Number 3
Year of Publication: 2014
Authors: Kanak Chandra Bora, Bichitra Kalita
10.5120/16776-6351

Kanak Chandra Bora, Bichitra Kalita . Particular Type of Hamiltonian Graphs and their Properties. International Journal of Computer Applications. 96, 3 ( June 2014), 31-36. DOI=10.5120/16776-6351

@article{ 10.5120/16776-6351,
author = { Kanak Chandra Bora, Bichitra Kalita },
title = { Particular Type of Hamiltonian Graphs and their Properties },
journal = { International Journal of Computer Applications },
issue_date = { June 2014 },
volume = { 96 },
number = { 3 },
month = { June },
year = { 2014 },
issn = { 0975-8887 },
pages = { 31-36 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume96/number3/16776-6351/ },
doi = { 10.5120/16776-6351 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:20:48.558405+05:30
%A Kanak Chandra Bora
%A Bichitra Kalita
%T Particular Type of Hamiltonian Graphs and their Properties
%J International Journal of Computer Applications
%@ 0975-8887
%V 96
%N 3
%P 31-36
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In this paper, various properties of particular type of Hamiltonian graph and it's edge-disjoint Hamiltonian circuits have been discussed. It has been found that the intersection graph obtained from Euler Diagram is not Hamiltonian. The graph H(3m + 7, 6m + 14) for m ? 1, which is planner, regular of degree four, non-bipartite but Hamiltonian graph , has perfect matching 4 with non- repeated edge for simultaneous changes of m= 2n+1 for n?0.

References
  1. R. Diestel, 2000. Graph Theory , Springer, New York .
  2. M. R. Garey, D. S. Johnson, 1997. Computers and Intractability, A Guid to the Theory of NP Completeness, Freeman, San Francisco.
  3. L. Lovasz 1979. Combinatorial problems and exercises, North-Holland, Amsterdam.
  4. Bora K. C. and Kalita B. , Exact Polynomial-time Algorithm for the Clique Problem and P = NP for Clique Problem, International Journal of Computer Application, June 2013, Volume 73, No. 8, pp. -19-23.
  5. Choudhury J. Kr. , Kalita B. , An Algorithm for Traveling Salesman Problem, Bulletin of Pure and Applied Sciences, Volume 30 E (Math & Stat. ) Issue (No. 1)2011: pp. - 111-118.
  6. Kalita B. , Sub-graphs of Complete Graph, International Conference of Foundation of Computer Science|FCS'06|, Las Vegus, USA,pp. -71-77.
  7. Dutta A. et al, "Regular Planar Sub-Graphs of Complete Graph and Their Application", International Journal of Applied Engineering Research ISSN 0973-4562 Volume 5 Number 3 Number 3 (2010) pp 377-386.
  8. Shih W. K. , et al, An O(n2 log n) time algorithm for Hamiltonian cycle problem on circular-arc graphs, SIAM J. Comput. 21 (1992) , pp. -1026-1046.
  9. Hung Ruo-Wei, et al, " The Hamiltonian Cycle Problem on Circular-Arc Graph", Proceedings of the International MultiConference of Engineers and Computer Scientists 2009 Vol I IMECS 2009, March 18 – 20, 2009, pp. -630-637.
  10. Wang Rui, et al, Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices, Discrete Applied Mathematics 155 (2007) 2312-2320.
  11. Cormen Thomas H. , et al, "Introduction to ALGORITHMS", Second Edition, Eastern Economy Edition, pp 979- 980.
  12. Du Lizhi, A Polynomial Time Algorithm for Hamilton Cycle (Path)", Proceeding of the International MultiConference of Engineers and Computer Scientists 2010 ,Vol 1, pp. -292-294.
  13. Povo V. , Sorting by prefix reversals, IAENG International Journal of Applied Mathemics, 40 (2010), pp. - 247-250.
  14. Hung Ruo-Wei, Constructing Two Edge-Disjoined Hamiltonian Cycles and Two-Equal Path Cover in Augmented Cubes, IAENG International Journal of Computer Science, 39 (2012), pp. -42-49.
  15. Kort J. B. J. M. De, Lower Bounds for Symmetric K-peripatetic Salesman Problems, Optimization, 22(1991), pp. - 113-122.
  16. Deo Narasingh, Graph Theory with Applications to Engineering and Computer Science, Prentice Hall of India Pvt. Ltd, 1986.
  17. Ayyaswamy S. K. and Koilraj S. , A Method of Finding Edge Disjoint Hamiltonian Circuits of Complete Graphs of Even Order, Indian J. Pure appl. Math. 32(12) : December 2001, pp. - 1893-1897.
  18. Gorbenko Anna and Popov Vladimir, The Problem of Finding Two Edge-Disjoint Hamiltonian Cycles, Applied Mathematical Sciences, Vol. 6, 2012, no. 132, pp. -6563 – 6566.
  19. Kalita, B. , A new set of non-planar graphs, Bull. Pure and Applied Sc. Vol. 24E(No-D, 2005, pp29-38.
  20. Hung R. W. and Chang M. S. , Solving the path cover problem on circular-arc graphs by using an approximation algorithm, Discrete Appl. Math. Vol. 154, 2006. , pp. 76-105.
  21. Hung R. W. and Chang M. S. , Finding a minimum path cover of a distance-hereditary graph in polynomial time, Discrete Appl. Math. Vol. 155, 2007, pp. 2242-2256.
  22. Park J. H. , One-to-one disjoint path covers in recursive circulants, Journal of KISS. , vol. 30, 2003, pp. - 691-689.
  23. Park J. H. , One-to-many disjoint path covers in a graph with faulty elements, in Proc. Of the International Computing and CombinatoricsConference(COCOON' 04), 2004, pp. 392-401.
  24. Park J. H. Park, et al, Many-to-many disjoint path covers in a graph with faulty elements, in Proc. Of the International Symposium on Algorithms and Computation (ISAA' 04. Pp. 742-753.
  25. Hung R. W. and Liao C. C. , Two-Edge- disjoint Hamiltonian cycles and Two – equal path partition in Augmented cubes, IMCS 2011, March, 16-18, pp. -197-201.
  26. Pathak R. , Kalita B. , "Properties of Some Euler Graphs Constructed from Euler Diagram", Int. Journal of Applied Sciences and Engineering Research, Vol. I, No. 2, 2012, pp. -232-237.
  27. Douglas B. West, "Introduction to Graph Theory", Second Edition, Pearson Education.
Index Terms

Computer Science
Information Sciences

Keywords

Hamiltonian Regular Edge-disjoint Hamiltonian circuits Perfect matching Intersection graph.