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 |
