A covering problem that is easy for trees but -complete for trivalent graphs

Abstract: By definition, a P2-graph is an undirected graph in which every vertex is contained in a path of length two. For such a graph, denotes the minimum number of paths of length two that cover all vertices of . We prove that and show that these upper and lower bounds are tight. Furthermore we show that every connected P2-graph contains a spanning tree such that . We present a linear time algorithm that produces optimal 2-path covers for trees. This is contrasted by the result that the decision problem is -complete for trivalent graphs. This graph theoretical problem originates from the task of searching a large database of biological molecules such as the Protein Data Bank (PDB) by content. [Copyright &y& Elsevier]