Single-source three-disjoint path covers in cubes of connected graphs |
| |
| Authors: | Jung-Heum Park Insung Ihm |
| |
| Affiliation: | 1. School of Computer Science and Information Engineering, The Catholic University of Korea, Bucheon, Republic of Korea;2. Department of Computer Science and Engineering, Sogang University, Seoul, Republic of Korea |
| |
| Abstract: | A k-disjoint path cover (k-DPC for short) of a graph is a set of k internally vertex-disjoint paths from given sources to sinks that collectively cover every vertex in the graph. In this paper, we establish a necessary and sufficient condition for the cube of a connected graph to have a 3-DPC joining a single source to three sinks. We also show that the cube of a connected graph always has a 3-DPC joining arbitrary two vertices. |
| |
| Keywords: | Disjoint path cover Hamiltonicity Graph embedding Cube of a graph Combinatorial problems |
| 本文献已被 ScienceDirect 等数据库收录！ |
