IJPAM: Volume 86, No. 6 (2013)


L. Nirmala Rani$^1$, Indra Rajasingh$^2$, Jennifer Rajkumari$^3$
$^1$Department of Mathematics
Karunya University, INDIA
$^2$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.

DOI: 10.12732/ijpam.v86i6.9 How to cite this paper?
International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2013
Volume: 86
Issue: 6