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

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 ∣ 0 ≤ i ≤ r − 1 } between any two...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2011-08, Vol.412 (35), p.4513-4530
Main Authors: Shih, Yuan-Kang, Kao, Shin-Shin
Format: Article
Language:English
Subjects:
[formula omitted]-ary [formula omitted]-cube
Applied sciences
Computer science
control theory
systems
Construction
Disjoint path cover
Exact sciences and technology
Graphs
Hamiltonian
Hypercube
Interconnection
Miscellaneous
Networks
Optimization
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ∣ 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 ∣ 0 ≤ i ≤ r − 1 } between any pair of vertices w and b from different partite sets of Q n k when k is even, such that ⋃ i = 0 r − 1 P i or ⋃ i = 0 r − 1 R i covers all vertices of Q n k for 1 ≤ r ≤ 2 n . In other words, we construct the one-to-one r -disjoint path cover of Q n k for any r with 1 ≤ r ≤ 2 n . The result is optimal since any vertex in Q n k has exactly 2 n neighbors.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2011.04.035