Article ID Journal Published Year Pages File Type
438541 Theoretical Computer Science 2013 24 Pages PDF
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
, , , ,