Vertex-fault-tolerant cycles embedding in 4-conditionally faulty folded hypercubes

详细信息    查看全文

• 作者：Che-Nan Kuo ^{cn.kuo@mail.toko.edu.tw" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Interconnection networks ; Folded hypercubes ; Cycles ; Vertex-fault-tolerant ; Conditionally faulty ; Fault-free
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 May 2016
• 年：2016
• 卷：205
• 期：Complete
• 页码：80-85
• 全文大小：414 K

文摘

A network is said to be g$g$-conditionally faulty if its every vertex has at least g$g$ fault-free neighbors, where g≥1$g\ge 1$. An n$n$-dimensional folded hypercube FQ_n$F{Q}_n$ is a well-known variation of an n$n$-dimensional hypercube Q_n$Q_n$, which can be constructed from Q_n$Q_n$ by adding an edge to every pair of vertices with complementary addresses. FQ_n$F{Q}_n$ for any odd n$n$ is known to be bipartite. In this paper, let 03bb" title="Click to view the MathML source">FF_v$F{F}_v$ denote the set of faulty vertices in FQ_n$F{Q}_n$, and let b4531a01509450a97ef63" title="Click to view the MathML source">F_FQn(e)$F_{F{Q}_n}\left(e\right)$ denote the set of faulty vertices which are incident to the end-vertices of any fault-free edge e∈E(FQ_n)$e\in E\left(F{Q}_n\right)$. Then, under the 4-conditionally faulty and |F_FQn(e)|≤n−3$\left|F_{F{Q}_n}\left(e\right)\right|\le n-3$, we consider for the vertex-fault-tolerant cycles embedding properties in FQ_n−FF_v$F{Q}_n-F{F}_v$, as follows:

1.

For n≥4$n\ge 4$, FQ_n−FF_v$F{Q}_n-F{F}_v$ contains a fault-free cycle of every even length from 4$4$ to 2ⁿ−2|FF_v|$2^n-2\left|F{F}_v\right|$, where b4501b4009c6a492c0334cd10e8" title="Click to view the MathML source">|FF_v|≤2n−7$\left|F{F}_v\right|\le 2n-7$;

2.

For n≥4$n\ge 4$ being even, FQ_n−FF_v$F{Q}_n-F{F}_v$ contains a fault-free cycle of every odd length from n+1$n+1$ to 2ⁿ−2|FF_v|−1$2^n-2\left|F{F}_v\right|-1$, where b4501b4009c6a492c0334cd10e8" title="Click to view the MathML source">|FF_v|≤2n−7$\left|F{F}_v\right|\le 2n-7$.