To search, Click
below search items.


All
Published Papers Search Service

Title

On Independence Problem of P2Graph

Author

Yaser AlMtawa, Munif Jazzer

Citation 
Vol. 9 No. 1 pp. 205211

Abstract

Let G be a graph and r be a positive integer r ¡Ã 1. Then the vertices of the rpath graph Pr(G) are the set of all paths of length r in G. Two vertices in Pr(G) are adjacent if and only if the intersection of the corresponding paths forms a path of length r1, and their union forms a path or cycle of length r+1. The 1history (or simply history) of a vertex in Pr(G) is a path p of length r in G. In this paper, the definition of a history is used in a new interpretation of the domination problem to study properties of the maximal independent sets in 2path graphs, and then to provide an algorithm for finding the maximum independence domination number in 2path graph of a tree T. The complexity of the algorithm is ¥è(n2), where n is the number of vertices in T.

Keywords

Path graph, maximum independent set, graph history, networks

URL

http://paper.ijcsns.org/07_book/200901/20090129.pdf

