Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1161.68684
Li, Tseng-Kuei; Tsai, Chang-Hsiung; Tan, Jimmy J.M.; Hsu, Lih-Hsing
Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes. (English)
[J] Inf. Process. Lett. 87, No. 2, 107-110 (2003). ISSN 0020-0190

Summary: A bipartite graph is bipancyclic if it contains a cycle of every even length from 4 to $|V(G)|$ inclusive. It has been shown that $Q_n$ is bipancyclic if and only if $n \geqslant 2$. In this paper, we improve this result by showing that every edge of $Q_n - E^{\prime}$ lies on a cycle of every even length from 4 to $|V(G)|$ inclusive where $E^{\prime}$ is a subset of $E(Q_n)$ with $|E^{\prime}|\leqslant n - 2$. The result is proved to be optimal. To get this result, we also prove that there exists a path of length $l$ joining any two different vertices $x$ and $y$ of $Q_n$ when $h(x,y) \leqslant l \leqslant|V(G)| - 1$ and $l - h(x,y)$ is even where $h(x,y)$ is the Hamming distance between $x$ and $y$.

MSC 2000:: *68R10 Graph theory in connection with computer science

Keywords: hypercube; Hamiltonian; bipancyclic; bipanconnected; interconnection networks

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]