Article ID Journal Published Year Pages File Type
4647205 Discrete Mathematics 2014 9 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,