標題: On the bipanpositionable bipanconnectedness of hypercubes
作者: Kung, Tzu-Liang
Lin, Cheng-Kuan
Liang, Tyne
Hsu, Lih-Hsing
Tan, Jimmy J. M.
資訊工程學系
Department of Computer Science
關鍵字: Hamiltonian laceable;Bipancyclic;Bipanpositionable;Interconnection network;Hypercube
公開日期: 1-Mar-2009
摘要: A bipartite graph G is bipanconnected if, for any two distinct vertices x and y of G, it contains an vertical bar x,y vertical bar-path of length l for each integer l satisfying d(G)(x, y) <= l <= vertical bar V(G)vertical bar - 1 and 2 vertical bar(l - d(G)(x, y)), where d(G)(x, y) denotes the distance between vertices x and y in G and V(G) denotes the vertex set of G. We say a bipartite graph G is bipanpositionably bipanconnected if, for any two distinct vertices x and y of G and for any vertex z is an element of V(G) - (x, y), it contains a path P(l,k) of length l Such that x is the beginning vertex of P(l,k), z is the (k + 1)-th vertex of P(l,k), and y is the ending vertex of P(l,k) for each integer l satisfying d(G)(x, z) + d(G)(y, z) <= l <= vertical bar V(G)vertical bar - 1 and 2 vertical bar(l - d(G)(x, z) - d(G)(y, z)) and for each integer k satisfying d(G)(x, z) <= k <= l -d(G)(y, z) and 2 vertical bar(k - d(G)(x, z)). In this paper, we prove that an n-cube is bipanpositionably bipanconnected if n >= 4. As a consequence, many properties of hypercubes, such as bipancyclicity, bipanconnectedness, bipanpositionable Hamiltonicity, etc., follow directly from our result. (C) 2008 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.tcs.2008.11.004
http://hdl.handle.net/11536/7599
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2008.11.004
期刊: THEORETICAL COMPUTER SCIENCE
Volume: 410
Issue: 8-10
起始頁: 801
結束頁: 811
Appears in Collections:Articles


Files in This Item:

  1. 000263945000014.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.