Disjoint path covers in cubes of connected graphs

作者：Park Jung Heum; Ihm Insung^*

来源：Discrete Mathematics, 2014, 325: 65-73.

DOI：10.1016/j.disc.2014.02.010

• Disjoint path cover
• Strong hamiltonicity
• Hamiltonian path
• Prescribed edge
• Cube of graph

Given a graph G, and two vertex sets S and T of size k each, a many-to-many k-disjoint path cover of G joining S and T is a collection of k disjoint paths between S and T that cover every vertex of G. It is classified as paired if each vertex of S must be joined to a designated vertex of T, 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.

• 出版日期2014-6-28