The week's pick
Random Articles
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
- R. Diestel, 2000. Graph Theory , Springer, New York .
- M. R. Garey, D. S. Johnson, 1997. Computers and Intractability, A Guid to the Theory of NP Completeness, Freeman, San Francisco.
- L. Lovasz 1979. Combinatorial problems and exercises, North-Holland, Amsterdam.
- 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.
- 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.
- Kalita B. , Sub-graphs of Complete Graph, International Conference of Foundation of Computer Science|FCS'06|, Las Vegus, USA,pp. -71-77.
- 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.
- 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.
- 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.
- Wang Rui, et al, Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices, Discrete Applied Mathematics 155 (2007) 2312-2320.
- Cormen Thomas H. , et al, "Introduction to ALGORITHMS", Second Edition, Eastern Economy Edition, pp 979- 980.
- 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.
- Povo V. , Sorting by prefix reversals, IAENG International Journal of Applied Mathemics, 40 (2010), pp. - 247-250.
- 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.
- Kort J. B. J. M. De, Lower Bounds for Symmetric K-peripatetic Salesman Problems, Optimization, 22(1991), pp. - 113-122.
- Deo Narasingh, Graph Theory with Applications to Engineering and Computer Science, Prentice Hall of India Pvt. Ltd, 1986.
- 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.
- 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.
- Kalita, B. , A new set of non-planar graphs, Bull. Pure and Applied Sc. Vol. 24E(No-D, 2005, pp29-38.
- 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.
- 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.
- Park J. H. , One-to-one disjoint path covers in recursive circulants, Journal of KISS. , vol. 30, 2003, pp. - 691-689.
- 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.
- 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.
- 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.
- 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.
- Douglas B. West, "Introduction to Graph Theory", Second Edition, Pearson Education.
Index Terms
Computer Science
Information Sciences
Keywords