Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
438541 | Theoretical Computer Science | 2013 | 24 Pages |
Abstract
Given two pairs 〈u, v〉 and 〈x, y 〉 of vertices of a graph G=(V,E)G=(V,E) and two integers l1l1 and l2l2 with l1+l2=|V(G)|−2l1+l2=|V(G)|−2, G is said to be satisfying the 2RP-property if there exist two disjoint paths P1P1 and P2P2 such that (1) P1P1 is a path joining u to v with l(P1)=l1l(P1)=l1, (2) P2P2 is a path joining x to y with l(P2)=l2l(P2)=l2, and (3) P1∪P2P1∪P2 spans G , where l(P)l(P) denotes the length of path P. In this paper, we show that an r -dimensional generalized hypercube, denoted by G(mr,mr−1,…,m1)G(mr,mr−1,…,m1), satisfies the 2RP-property except some special conditions, where mi⩾4mi⩾4 for all 1⩽i⩽r1⩽i⩽r.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dyi-Rong Duh, Yao-Chung Lin, Cheng-Nan Lai, Yue-Li Wang,