On the bipanpositionable bipanconnectedness of hypercubes

Tzu-Liang Kung, Cheng-Kuan Lin, Tyne Liang, Jiann-Mean Tan, Lih-Hsing Hsu

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

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,P-k of length l Such that x is the beginning vertex of P-l,P-k, z is the (k + 1)-th vertex of P-l,P-k, and y is the ending vertex of P-l,P-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.
Original languageAmerican English
Pages (from-to)801-811
Number of pages11
JournalTheoretical Computer Science
Volume410
Issue number8-10
DOIs
StatePublished - 1 Mar 2009

Keywords

  • Hamiltonian laceable; Bipancyclic; Bipanpositionable; Interconnection network; Hypercube

Fingerprint Dive into the research topics of 'On the bipanpositionable bipanconnectedness of hypercubes'. Together they form a unique fingerprint.

Cite this