Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs |
| |
| Authors: | Xie-Bin Chen |
| |
| Affiliation: | Department of Mathematics and Information Science, Zhangzhou Teachers College, Zhangzhou, Fujian 363000, China |
| |
| Abstract: | Let Wn denote any bipartite graph obtained by adding some edges to the n-dimensional hypercube Qn, and let S and T be any two sets of k vertices in different partite sets of Wn. In this paper, we show that the graph Wn has k vertex-disjoint (S,T)-paths containing all vertices of Wn if and only if k=2n−1 or the graph Wn−(S∪T) has a perfect matching. Moreover, if the graph Wn−(S∪T) has a perfect matching M, then the graph Wn has k vertex-disjoint (S,T)-paths containing all vertices of Wn and all edges in M. And some corollaries are given. |
| |
| Keywords: | Hypercube Vertex-disjoint paths Hamiltonian path Matching Folded hypercube Interconnection network |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
