標題: The Mutually Independent Bipanconnected Property for Hypercube
作者: Shih, Yuan-Kang
Tan, Jimmy J. M.
Hsu, Lih-Hsing
資訊工程學系
Department of Computer Science
公開日期: 2009
摘要: A graph is denoted by G with the vertex set V(G) and the edge set E(G). A path P = < vo,vi, ... ,v(m)> is a sequence of adjacent vertices. Two paths with equal length Pi = < u(1), u(2), ... ,U(m)> and P(2) = (v(0), v(1), ... , v(m)) from a to b are independent if u(1) = v1 = a, u(m) = v(m) = b, and u(i) not equal v(i). for 2 <= i <= m - 1. Paths with equal length {Pi}(i=1)(n) from a to b are mutually independent if they are pairwisely independent. Let u and v be two distinct vertices of a bipartite graph G, and let 1 be a positive integer length, d(G)(u, v) <= 1 <= |V(G) - 1| with (l - dc(u, v)) being even. We say that the pair of vertices u, v is (m,1)-mutually independent bipanconnected if there exist m mutually independent paths {P(i)(l)}(i=1)(m) with length l from u to v. In this paper, we explore yet another strong property of the hypercubes. We prove that every pair of vertices u and v in the n-dimensional hypercube, with d(Qn)(u,v) >= n - 1, is (n - 1, l)-mutually independent bipanconnected for every l, d(Qn)(u, v) <= 1 <= |V(Q(n))-1| with (l - d(Qn)(u, v)) being even. As for d(Qn)(u,v)<= n - 2, it is also (n - 1, l)-mutually independent bipanconnected if l >= d(Qn) (u, v) + 2, and is only (l, l)-mutually independent bipanconnected if l= d(Qn)(u,v).
URI: http://hdl.handle.net/11536/14512
http://dx.doi.org/10.1109/I-SPAN.2009.88
ISBN: 978-1-4244-5403-7
DOI: 10.1109/I-SPAN.2009.88
期刊: 2009 10TH INTERNATIONAL SYMPOSIUM ON PERVASIVE SYSTEMS, ALGORITHMS, AND NETWORKS (ISPAN 2009)
起始頁: 606
結束頁: 609
Appears in Collections:Conferences Paper


Files in This Item:

  1. 000291013200106.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.