کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647205 | 1632417 | 2014 | 9 صفحه PDF | دانلود رایگان |
Given a graph GG, and two vertex sets SS and TT of size kk each, a many-to-many kk-disjoint path cover of GG joining SS and TT is a collection of kk disjoint paths between SS and TT that cover every vertex of GG. It is classified as paired if each vertex of SS must be joined to a designated vertex of TT, or unpaired if there is no such constraint. In this article, we first present a necessary and sufficient condition for the cube of a connected graph to have a paired 2-disjoint path cover. Then, a corresponding condition for the unpaired type of 2-disjoint path cover problem is immediately derived. It is also shown that these results can easily be extended to determine if the cube of a connected graph has a hamiltonian path from a given vertex to another vertex that passes through a prescribed edge.
Journal: Discrete Mathematics - Volume 325, 28 June 2014, Pages 65–73