IJRCS – Volume 4 Issue 2 Paper 2

Posted on by Researchscripteditor

ON HAMILTONIAN CYCLE OF PLANAR 3 TREES

Author’s Name : S Ranjith Kumar | S Zubair | C Dinesh | K Sankar Ganesh

Volume 04 Issue 02  Year 2017  ISSN No:  2349-3828  Page no: 5-8

12

Abstract:

A k-tree is a chordal graph all of whose maximal cliques are the same size k + 1 and all of whose minimal clique separators are also all the same size k. If a 3-Tree chordal graph G has a planar embedding, then it is called as planar 3-Trees. A planar graph is a graph that can be embedded in the plane. Given a chordal 3-tree G , compute an embedding on the plane without edge crossings. In this work, we investigate local properties that provide information about the global cycle structure of a graph. There exists a closed walk on the graph along the edges such that visited each vertex exactly once and cover all the vertices in a single closed walk. We present a linear time algorithm to characterize the Hamiltonianicity of a 3-tree, and polynomial time algorithm to recognize the Hamiltonian circuit in the planar 3-tree. We begin by defining the global cycle properties that we shall consider. The order (number of vertices) of a graph G is denoted by n. A graph G is Hamiltonian if G has a cycle of length n. We emulate flexibility and feasibility by giving more features into the UI. Primary objective is to establish a structural properties and characterization of planar 3-trees and Hamiltonian cycle. Hamiltonian cycle has more characterization on planar 3-trees with respect to simplicial ordering and perfect elimination ordering.

Keywords:

Graph, Embedding, Hamiltonian Cycle, Planar 3-Tree

References:

  1. Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, and Thomas Thierauf. Planarizing gadgets for perfect matching do not exist.
  2. ACM Trans. Comput. Theory, 8(4):14:1{14:15, July 2016.Louis Ibarra.A simple algorithm to _nd hamiltonian cycles in proper interval graphs.
  3. Inf. Process. Lett., 109(18):1105{1108, August  2009.Ken ichi Kawarabayashi and Kenta Ozeki.4-connected projective-planar graphs are hamiltonian-connected
  4. Journal of Combinatorial Theory, Series B,112:36 { 69, 2015.Tao Jiang.Planar hamiltonian chordal graphs are cycle extendable.
  5. Discrete Mathematics, 257(2{3):441 { 444, 2002.Kleitman and Combinatorics: A Celebration. Adam Kabela and Tom_a_s Kaiser.10-tough chordal graphs are hamiltonian (extended abstract).
  6. Electronic Notes in Discrete Mathematics,49:331 { 336, 2015.The Eight European Conference on Combinatorics,Graph Theory and Applications, EuroComb 2015.B. S. Panda and Sajal K. Das. Parallel recognition algorithms for Chordal_planar graphs and planar k-trees.
  7. J. Parallel Distrib. Comput., 65(8):922{926,August 2005.Zhendong Shao and Roger K. Yeh.The -labeling on planar graphs.
  8. Applied Mathematics Letters, 20(2):222 {226, 2007.Jakub Teska.On 2-walks in chordal planar graphs.Discrete Math., 309(12):4017{4026, June 2009.