To search, Click below search items.

 

All Published Papers Search Service

Title

On Independence Problem of P2-Graph

Author

Yaser Al-Mtawa, Munif Jazzer

Citation

Vol. 9  No. 1  pp. 205-211

Abstract

Let G be a graph and r be a positive integer r ≥ 1. Then the vertices of the r-path 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 r-1, and their union forms a path or cycle of length r+1. The 1-history (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 2-path graphs, and then to provide an algorithm for finding the maximum independence domination number in 2-path 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