Fault-tolerant panconnectivity of augmented cubes

Abstract

The augmented cube AQ_n is a variation of the hypercube Q_n. This paper considers the panconnectivity of AQ_n (n ⩾ 3) with at most 2n−5 faulty vertices and/or edges and shows that, for any two fault-free vertices u and v with distance d in AQ_n, there exist fault-free uv-paths of every length from d + 2 to 2ⁿ − f − 1, where f is the number of faulty vertices in AQ_n. The proof is based on an inductive construction.

Keywords

Path / pancyclic / hamiltonian connected / panconnectivity / augmented cube / fault tolerance

References

[1] Chen Y. -Y., Duh D. -R., Ye T. -L., Fu J. -S. Weak-vertex-pancyclicity of (n, k)-star graphs. Theoretical Computer Science, 2008, 396(3): 191-199.

[2] Choudum A. A., Sunitha V. Augmented cubes. Networks, 2002, 40(2): 71-84.

[3] Choudum S. A., Sunitha V. Distance and short parallel paths in augmented cubes. Electronic Notes in Discrete Mathematics, 2003, Amsterdam: Elsevier.

[4] Fu J. -S. Fault-free hamiltonian cycles in twisted cubes with conditional link faults. Theoretical Computer Science, 2008, 407(1–3): 318-329.

[5] Hsieh S. -Y. Embedding longest fault-free paths onto star graphs with more vertex faults. Theoretical Computer Science, 2005, 337(1–3): 370-378.

[6] Hsieh S. -Y., Chen G. -H., Ho C.-W. Longest fault-free paths in star graphs with vertex faults. Theoretical Computer Science, 2001, 262: 215-227.

[7] Hsu H. -C., Chiang L. -C., Tan J. J. M., Hsu L. -H. Fault hamiltonicity of augmented cubes. Parallel Computing, 2005, 31(1): 131-145.

[8] Hsu H. -C., Lai P. -L., Tsai C. -H. Geodesic pancyclicity and balanced pancyclicity of augmented cubes. Information Processing Letters, 2007, 101: 227-232.

[9] Lin C. -K., Huang H.-M., Hsu L. -H. The super connectivity of the pancake graphs and the super laceability of the star graphs. Theoretical Computer Science, 2005, 339(2–3): 257-271.

[10] Ma M. -J., Liu G. -Z., Xu J. -M. Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes. Parallel Computing, 2007, 33(1): 36-42.

[11] Ma M. -J., Liu G. -Z., Xu J. -M. Fault-tolerant embedding of paths in crossed cubes. Theoretical Computer Science, 2008, 407(1–3): 110-116.

[12] Ma M. -J., Liu G. -Z., Xu J. -M. The super connectivity of augmented cubes. Information Processing Letters, 2008, 106(2): 59-63.

[13] Park J. -H., Chwa K. -Y. Recursive circulants and their embeddings among hypercubes. Theoretical Computer Science, 2000, 244: 35-62.

[14] Park J. H., Kim H. C., Lim H. S. Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements. Theoretical Computer Science, 2007, 377(1–3): 170-180.

[15] Tsai C. H. Linear array and ring embeddings in conditional faulty hypercubes. Theoretical Computer Science, 2004, 314(3): 431-443.

[16] Tsai P. -Y., Fu J. -S., Chen G. -H. Edge-fault-tolerant Hamiltonicity of pancake graphs under the conditional fault model. Theoretical Computer Science, 2008, 409(3): 450-460.

[17] Tsai P. -Y., Fu J. -S., Chen G. -H. Fault-free longest paths in star networks with conditional link faults. Theoretical Computer Science, 2009, 410(8–10): 766-775.

[18] Wang W. -W., Ma M. -J., Xu J. -M. Fault-tolerant pancyclicity of augmented cubes. Information Processing Letters, 2007, 103(2): 52-56.

[19] Xu J. -M. Topological Structure and Analysis of Interconnection Networks, 2001, Dordrecht/Boston/London: Kluwer Academic Publishers.

[20] Xu J. -M., Ma M. -J. A survey on cycle and path embedding in some networks. Front Math China, 2009, 4(2): 217-252.

[21] Xu M., Xu J. -M. The forwarding indices of augmented cubes. Information Processing Letters, 2007, 101(5): 185-189.