IJPAM: Volume 86, No. 6 (2013)
HOLE IN SIERPINSKY GRAPH
Department of Mathematics
Karunya University, INDIA
School of Advanced Sciences
VIT University, INDIA
Abstract. Path ecomposition and Path width which are closely analogous to tree decomposition and tree width play a key role in the theory of graph minors. They have many applications in VLSI Design, Graph Drawing, Compiler Design and Linguistics [#!1!#]. Many problems in graph algorithm can be solved effectively on graphs of bounded path width by using dynamic programming on a path decomposition of the graph [#!2!#]. Decomposition may also be used to measure the space complexity of dynamic programming algorithms on graphs of bounded tree width [#!3!#]. Once path decomposition has been found, a topological ordering of width w (if one exists) can be found using dynamic programming in linear time [#!4!#]. In this paper we discuss about the induced path decomposition, the hole and the positions of every vertex of the Sierpinsky Graph w.r.t the hole.
Received: May 9, 2013
AMS Subject Classification:
Key Words and Phrases: induced path, acyclic induced path, induced path decomposition, hole, sierpinsky graph
Download paper from here.
DOI: 10.12732/ijpam.v86i6.9 How to cite this paper?
Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395