Edge-bipancyclicity of a hypercube with faulty vertices and edges

Sun Yuan Hsieh, Tzu Hsiung Shen

研究成果: Article同行評審

46 引文 斯高帕斯(Scopus)

摘要

A bipartite graph G = (V, E) is said to be bipancyclic if it contains a cycle of every even length from 4 to | V |. Furthermore, a bipancyclic G is said to be edge-bipancyclic if every edge of G lies on a cycle of every even length. Let Fv (respectively, Fe) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Qn. In this paper, we show that every edge of Qn - Fv - Fe lies on a cycle of every even length from 4 to 2n - 2 | Fv | even if | Fv | + | Fe | ≤ n - 2, where n ≥ 3. Since Qn is bipartite of equal-size partite sets and is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free cycle obtained are worst-case optimal.

原文English
頁(從 - 到)1802-1808
頁數7
期刊Discrete Applied Mathematics
156
發行號10
DOIs
出版狀態Published - 2008 5月 28

All Science Journal Classification (ASJC) codes

  • 離散數學和組合
  • 應用數學

指紋

深入研究「Edge-bipancyclicity of a hypercube with faulty vertices and edges」主題。共同形成了獨特的指紋。

引用此