Induced-path partition on graphs with special blocks

AbstractIn a graph, an induced path is a path v0,v1,…,vr in which a vertex vi is adjacent to another vertex vj if and only if |i−j|=1. An induced-path partition of a graph is a collection of vertex-disjoint induced paths that cover all vertices of the graph. The induced-path-partition problem is to determine the minimum cardinality of an induced-path partition of a graph. This paper presents an O(|V|+|E|)-time algorithm for the induced-path-partition problem on graphs whose blocks are complete graphs, cycles or complete bipartite graphs