L. Nirmala Rani, Indra Rajasingh, Jennifer Rajkumari
Department of Mathematics
Karunya University, INDIA
School of Advanced Sciences
VIT University, INDIA
Stanford University
California, USA

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.