To search, Click below search items.


All Published Papers Search Service


On Independence Problem of P2-Graph


Yaser Al-Mtawa, Munif Jazzer


Vol. 9  No. 1  pp. 205-211


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.


Path graph, maximum independent set, graph history, networks