On Independence Problem of P_2-Graph

摘要

Let G be a graph and r be a positive integer r ≥ 1. Then the vertices of the r-path graph P_r(G) are the set of all paths of length r in G. Two vertices in P_r(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 P_r(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 θ(n~2), where n is the number of vertices in T.