×

Vertex-disjoint paths joining adjacent vertices in faulty hypercubes. (English) Zbl 1434.68351

Summary: Let \(Q_n\) denote the \(n\)-dimensional hypercube and the set of faulty edges and faulty vertices in \(Q_n\) be denoted by \(F_e\) and \(F_v\), respectively. In this paper, we investigate \(Q_n\) \((n \geq 3)\) with \(| F_e | + | F_v | \leq n - 3\) faulty elements, and demonstrate that there are two fault-free vertex-disjoint paths \(P [a, b]\) and \(P [c, d]\) satisfying that \(2 \leq \ell(P [a, b]) + \ell(P [c, d]) \leq 2^n - 2 | F_v | - 2\), where \(2 |(\ell(P [a, b]) + \ell(P [c, d]))\), \((a, b),(c, d) \in E(Q_n)\). The contribution of this paper is: (1) we can quickly obtain the interesting result that \(Q_n - F_e\) is bipancyclic, where \(| F_e | \leq n - 2\) and \(n \geq 3\); (2) this result is a complement to X.-B. Chen’s part result [Inf. Sci. 179, No. 18, 3110–3115 (2009; Zbl 1193.68050)] in that our result shows that there are all kinds of two disjoint-free \((S, T)\)-paths which contain \(4, 6, 8, \ldots, 2^n - 2 | F_v |\) vertices respectively in \(Q_n\) when \(S = \{a, c \}, T = \{b, d \}\), and \((a, b),(c, d) \in E(Q_n)\). Our result is optimal with respect to the number of fault-tolerant elements.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68M15 Reliability, testing and fault tolerance of networks and computer systems

Citations:

Zbl 1193.68050
Full Text: DOI

References:

[1] Chang, N.-W.; Hsieh, S.-Y., Fault-tolerant bipancyclicity of faulty hypercubes under the generalized conditional-fault model, IEEE Trans. Commun., 59, 12, 3400-3409 (2011)
[2] Chen, X.-B., Many-to-many disjoint paths in faulty hypercubes, Inf. Sci., 179, 3110-3115 (2009) · Zbl 1193.68050
[3] Chen, X.-B., Paired many-to-many disjoint path covers of the hypercubes, Inf. Sci., 236, 218-223 (2013) · Zbl 1284.05274
[4] Cheng, D.; Hao, R.-X.; Feng, Y.-Q., Embedding even cycles on folded hypercubes with conditional faulty edges, Inf. Process. Lett., 115, 945-949 (2015) · Zbl 1338.68215
[5] Jo, S.; Park, J.-H.; Chwa, K.-Y., Paired many-to-many disjoint path covers in faulty hypercubes, Theor. Comput. Sci., 513, 1-24 (2013) · Zbl 1352.68195
[6] Kung, T.-L.; Chen, H.-C., Complete cycle embedding in crossed cubes with two-disjoint-cycle-cover pancyclicity, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E98.A, 12, 2670-2676 (2015)
[7] Kuo, C.-N.; Hsieh, S.-Y., Pancyclicity and bipancyclicity of conditional faulty folded hypercubes, Inf. Sci., 180, 15, 2904-2914 (2010) · Zbl 1205.68097
[8] Leighton, F. T., Introduction to Parallel Algorithms and Architecture: Arrays, Trees, Hypercubes (1992), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA · Zbl 0743.68007
[9] Li, T.-K.; Tsai, C.-H.; Tan, J. J.M.; Hsu, L.-H., Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes, Inf. Process. Lett., 87, 107-110 (2003) · Zbl 1161.68684
[10] Lipták, L.; Cheng, E.; Kim, J.-S.; Kim, S. W., One-to-many node-disjoint paths of hyper-star networks, Discrete Appl. Math., 160, 2006-2014 (2012) · Zbl 1247.68022
[11] Ma, M.; Liu, G.; Pan, X., Path embedding in faulty hypercubes, Appl. Math. Comput., 192, 233-238 (2007) · Zbl 1193.05099
[12] Shih, Y.-K.; Kao, S.-S., One-to-one disjoint path covers on \(k\)-ary \(n\)-cubes, Theor. Comput. Sci., 412, 4513-4530 (2011) · Zbl 1223.68086
[13] Tsai, C.-H.; Lai, Y.-C., Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes, Inf. Sci., 177, 5590-5597 (2007) · Zbl 1132.68019
[14] Tsai, C.-H., Cycles embedding in hypercubes with node failures, Inf. Process. Lett., 102, 242-246 (2007) · Zbl 1184.68054
[15] Zhang, S.; Wang, S., Mang-to-many disjoint path covers in \(k\)-ary \(n\)-cubes, Theor. Comput. Sci., 491, 103-118 (2015) · Zbl 1277.68040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.