×

Fault-tolerant panconnectivity of augmented cubes \(\mathit{AQ}_n\). (English) Zbl 1429.68030

An interconnection network can be represented by a graph \(G\) with \(V(G)\) the vertex set and \(E(G)\) the edge set. A graph \(G\) of order \(n\) is said to be panconnected if for any pair of distinct vertices \(u\) and \(v\) with distance \(d\), there exists a path \(P_{uv}\) of length \(l\) for every \(l\) with \(d \leq l \leq 2^{n}-1\). The graph \(G\) is \(k\)-fault-tolerant panconnected if \(G-F\) remains panconnected for any \(F \subseteq V(G) \cup E(G)\) with \(\vert F \vert \leq k\).
In [H. Wang et al., Front. Math. China 4, No. 4, 697–719 (2009; Zbl 1184.05073)], it was proved that the hypercube \(AQ_{n}\) is \((2n-5)\)-fault-tolerant panconnected for \(n \geq 3\). The paper under review improves this result by proving:
Theorem 4.1. If \(F \subseteq V(AQ_{n}) \cup E(AQ_{n})\) with \(\vert F \vert \leq 2n-4\), then for any two distinct fault-free vertices \(u\) and \(v\) with distance \(d\), there exists a fault-free path \(P_{uv}\) of length \(l\) for each \(l\) with \(\max\{d+2,4\} \leq l \leq 2^{n} - f_{v}-1\) in \(AQ_{n} - F(n\geq 4)\), where \(f_{v}\) stands for the number of faulty vertices in \(AQ_{n}\).

MSC:

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

Citations:

Zbl 1184.05073
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lee, C. M.et al., Embedding Hamiltonian paths in augmented cubes with a required vertex in a fixed position, Comput. Math. Appl.58 (2009) 1762-1768. · Zbl 1189.05097
[2] Lin, C. K.et al., Super spanning connectivity of augmented cubes, Ars Comb.104 (2012) 161-177. · Zbl 1274.05269
[3] Zhou, D. F.et al., Cycles embedding in exchanged crossed cube, Int. J. Found. Comput. Sci.28(1) (2017) 61-76. · Zbl 1408.68028
[4] Hsu, H. C.et al., Fault hamiltonicity of augmented cubes, Parallel Computing31(1) (2005) 131-145.
[5] Hsu, H. C., Lai, P. L. and Tsai, C. H., Geodesic pancyclicity and balanced pancyclicity of augmented cubes, Information Processing Letters101 (2007) 227-232. · Zbl 1183.05043
[6] Wang, H. L., Wang, J. W. and Xu, J. M., Fault-tolerant panconnectivity of augmented cubes, Front. Math. China4(4) (2009) 697-719. · Zbl 1184.05073
[7] Chan, H. C.et al., Geodesic-pancyclicity and fault-tolerant panconnectivity of augmented cubes, Appl. Math. Comput.207 (2009) 333-339. · Zbl 1191.05058
[8] J. Bondy and U. Murty, Graph Theory with Applications, New York: North-Holland (1976). 377(1-3) (2007) 170-180. · Zbl 1226.05083
[9] Fan, J., Lin, X. and Jia, X., Optimal path embedding in crossed cubes, IEEE Trans. Parallel and Distributed Systems16(12) (2005) 1190-1200.
[10] Fan, J., Jia, X. and Lin, X., Optimal embeddings of paths with various lengths in twisted cubes, IEEE Trans. Parallel and Distributed Systems18(4) (2007) 511-521.
[11] Fan, J. and Jia, X., Edge-pancyclicity and path-embeddability of bijective connection graphs, Inform. Sci.178(1) (2008) 341-351. · Zbl 1128.68075
[12] Fan, J.et al., Optimal fault-tolerant embedding of paths in twisted cubes, J. Parallel Distrib. Comput.67(2) (2007) 205-214. · Zbl 1158.68336
[13] Fan, J. and Jia, X., Embedding meshes into crossed cubes, Inform. Sci.177(15) (2007) 3151-3160. · Zbl 1122.68013
[14] Wang, X.et al., Embedding meshes into twisted-cubes, Inform. Sci.181(14) (2011) 3085-3099. · Zbl 1218.68111
[15] Han, Y.et al., Embedding meshes into locally twisted cubes, Inform. Sci.180 (2010) 3794-3805. · Zbl 1205.68036
[16] Chang, J. M. and Yang, J. S., Fault-tolerant cycle-embedding in alternating group graphs, Applied Mathematics and Computation197(4) (2008) 760-767. · Zbl 1148.05049
[17] Xu, J. M. and Ma, M. J., A survey on cycle and path embedding in some networks, Front. Math. China4(2) (2009) 217-252. · Zbl 1176.90081
[18] Fu, J. S., Edge-fault-tolerant vertex-pancyclicity of augmented cubes, Inf. Process. Lett.110 (2010) 439-443. · Zbl 1229.68008
[19] Bae, M. M. and Bose, B., Edge disjoint hamiltonian cycles in \(k\)-ary \(n\)-cubes and hypercubes, IEEE Trans. Computers52(10) (2003) 1271-1284.
[20] Ma, M., Liu, G. and Xu, J., Fault-tolerant embedding of paths in crossed cubes, Theoretical Computer Science407(11) (2008) 110-116. · Zbl 1152.68010
[21] Ma, M., Liu, G. and Xu, J. M., The super connectivity of augmented cubes, Inf. Process. Lett.106 (2008) 59-63. · Zbl 1186.68339
[22] Xu, M. and Xu, J. M., The forwarding indices of augmented cubes, Inf. Process. Lett.101 (2007) 185-189. · Zbl 1185.05141
[23] Ma, M. J., Liu, G. Z. and Xu, J. M., Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes, Parallel Computing33(1) (2007) 36-42.
[24] Chan, M., The distinguishing number of the augmented cube and hypercube powers, Discrete Math.308(11) (2008) 2330-2336. · Zbl 1154.05029
[25] Wagh, M. and Guzide, O., Mapping cycles and trees on wrap-around butterfly graphs, SIAM J. Comput.35(3) (2006) 741-765. · Zbl 1095.68004
[26] Kulasinghe, P. and Bettayeb, S., Embedding binary trees into crossed cubes, IEEE Trans. Comput.44(7) (1995) 923-929. · Zbl 1053.68585
[27] Lo, R. S. and Chen, G. H., Embedding hamiltonian paths in faulty arrangement graphs with the backtracking method, IEEE Transactions on Parallel and Distributed Systems12(2) (2001) 209-222.
[28] Hsieh, S. Y. and Yu, P. Y., Cycle embedding on twisted cubes, International Conference on Parallel and Distributed Computing Applications and Technologies (PDCAT 06), IEEE Press, (12) (2006) 102-104.
[29] Hsieh, S. Y. and Chang, N. W., Hamiltonian path embedding and pancyclicity on the Mobius cube with faulty nodes and faulty edges, IEEE Transactions on Computers55(7) (2006) 854-863.
[30] Hsieh, S. Y. and Shiu, J. Y., Cycle embedding of augmented cubes, Applied Mathematics and Computation191 (2007) 314-319. · Zbl 1193.05098
[31] Hsieh, S. Y. and Cian, Y. R., Conditional edge-fault Hamiltonicity of augmented cubes, Inform. Sci.180 (2010) 2596-2617. · Zbl 1209.68375
[32] Choudum, S. A. and Sunitha, V., Augmented cubes, Networks40(2) (2002) 71-84. · Zbl 1019.05052
[33] S. A. Choudum and V. Sunitha, Distance and short parallel paths in augmented cubes, Electronic Notes in Discrete Mathematics15(66) (electronic). Electron Notes Discrete Math., Vol. 15 (Amsterdam: Elsevier, 2003). · Zbl 1259.05163
[34] S. A. Choudum and V. Sunitha, Wide-diameter of augmented cubes. Technical Report. Department of Mathematics, Indian Institute of Technology Madras, Chennai, November 2000. · Zbl 1163.05024
[35] S. A. Choudum and V. Sunitha, Automorphisms of augmented cubes. Technical Report. Department of Mathematics, Indian Institute of Technology Madras, Chennai, March 2001. · Zbl 1163.05024
[36] Wang, W. W., Ma, M. J. and Xu, J. M., Fault-tolerant pancyclicity of augmented cubes, Information Processing Letters103(2) (2007) 52-56. · Zbl 1185.05140
[37] Fang, W. C., Hsu, C. C. and Wang, C. M., On the fault-tolerant embeddings of complete binary trees in the mesh interconnection networks, Inform. Sci.151 (2003) 51-70. · Zbl 1012.68531
[38] Xu, X. R.et al., Fault-tolerant edge-pancyclicity of locally twisted cubes, Inform. Sci.181(11) (2011) 2268-2277. · Zbl 1216.68058
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.