Histories and Domination of Iterated Path Graphs

In the last decades, many research works on graph operators have appeared. Examples of such operators are line graph, clique graph, block graph and many others. When studying such operators, several questions immediately arise, such as which graphs are fixed under a given operator or what are the properties of iterated graphs. The line graph operator is probably the most studied graph operator. Iterations of line graphs are frequently used as models for communication networks. There are many generalizations of the line graph operator. One of them is a path graph operator. In this research, some important properties of path graph operator are addressed. These properties include histories, convergence, and divergence of iterated path graphs. However, the main emphasis is on the 2-path graph operator. Furthermore, the concept of history is utilized to derive a closed-form formula that calculates the independence domination number of 2-path graph for any tree graph. Then an efficient algorithm is designed, analyzed, and implemented toward evaluating this number.