کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420501 | 683951 | 2008 | 12 صفحه PDF | دانلود رایگان |
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, pc(Γ) denotes the minimum number of paths of length two that cover all nn vertices of ΓΓ. We prove that ⌈n/3⌉≤pc(Γ)≤⌊n/2⌋ and show that these upper and lower bounds are tight. Furthermore we show that every connected P2-graph ΓΓ contains a spanning tree TT such that pc(Γ)=pc(T). We present a linear time algorithm that produces optimal 2-path covers for trees. This is contrasted by the result that the decision problem pc(Γ)=?n/3 is NP-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.
Journal: Discrete Applied Mathematics - Volume 156, Issue 15, 6 August 2008, Pages 2855–2866