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.