Independence Number in Path Graphs

Martin Knor

Department of Mathematics, Faculty of Civil Engineering
Slovak University of Technology, Radlinskeho 11, 813 68 Bratislava, Slovakia
Ľudovít Niepel

Department of Mathematics & Computer Science, Faculty of Science
Kuwait University, P. O. Box 5969, Safat 13060, Kuwait

keywords: Path graph, independence number, iterated line graph, graph dynamics, (non)deterministic algorithm

In the paper we present results, which allow us to compute the independence numbers of P_2-path graphs and P_3-path graphs of special graphs. As P_2(G) and P_3(G) are subgraphs of iterated line graphs L2(G) and L3(G), respectively, we compare our results with the independence numbers of corresponding iterated line graphs.

reference: Vol. 23, 2004, No. 2, pp. 179–187

read full article
download full article

Computing and Informatics

formerly Computers and Artificial Intelligence

Independence Number in Path Graphs