A covering problem that is easy for trees but image-complete for trivalent graphs Original Research Article

By definition, a P2-graph image is an undirected graph in which every vertex is contained in a path of length two. For such a graph, image denotes the minimum number of paths of length two that cover all image vertices of image. We prove that image and show that these upper and lower bounds are tight. Furthermore we show that every connected P2-graph image contains a spanning tree image such that image. We present a linear time algorithm that produces optimal 2-path covers for trees. This is contrasted by the result that the decision problem image is image-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.