Independence Number in Path Graphs

Authors

  • Martin Knor
  • Ľudovít Niepel

Keywords:

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

Abstract

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 $L^2(G)$ and $L^3(G)$, respectively, we compare our results with the independence numbers of corresponding iterated line graphs.

Downloads

Download data is not yet available.

Downloads

Published

2012-02-06

How to Cite

Knor, M., & Niepel, Ľudovít. (2012). Independence Number in Path Graphs. COMPUTING AND INFORMATICS, 23(2), 179–187. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/414