Independence and Domination in Path Graphs of Trees
keywords: Path graph, dominating set, independent set
The problems of determining the maximum cardinality of an independent set of vertices and the minimum cardinality of a maximal independent set of vertices of a graph are known to be NP-complete. We provide efficient algorithms for finding these values for path graphs of trees.
reference: Vol. 27, 2008, No. 4, pp. 581–591
