One-to-one disjoint path covers on k-ary n-cubes

檔案

日期

2011-08-12

類型

期刊名稱

THEORETICAL COMPUTER SCIENCE

卷期與頁次

第 412 卷第 35 期,頁 4513–4530

ISSN

0304-3975

語言

英文

摘要

The k-ary n-cube, Q(n)(k) is one of the most popular interconnection networks. Let n >= 2 and k >= 3. It is known that Q(n)(k) is a nonbipartite (resp. bipartite) graph when k is odd (resp. even). In this paper, we prove that there exist r vertex disjoint paths {P(i) vertical bar 0 <= i <= r - 1} between any two distinct vertices u and v of Q(n)(k) when k is odd, and there exist r vertex disjoint paths {R(i) vertical bar 0 <= i <= r - 1} between any pair of vertices to and b from different partite sets of Q(n)(k) when k is even, such that boolean OR(r-1)(i=0) P(i) or boolean OR(r-1)(i=0) R(i) covers all vertices of Q(n)(k) for 1 <= r <= 2n. In other words, we construct the one-to-one r-disjoint path cover of Q(n)(k) for any r with 1 <= r <= 2n. The result is optimal since any vertex in Q(n)(k) has exactly 2n neighbors. (C) 2011 Elsevier B.V. All rights reserved.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Shih, Y.-K., & Kao, S.-S. (2011). One-to-one disjoint path covers on k-ary n-cubes. THEORETICAL COMPUTER SCIENCE, 412(35), 4513–4530. https://doi.org/10.1016/j.tcs.2011.04.035

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/20343