×
Hu, Xiaolan; Liu, Huiqing; Pan, Xiang-Feng

Fault-free Hamilton cycles in burnt pancake graphs with conditional edge faults. (English) Zbl 1288.05147

Discrete Appl. Math. 169, 152-161 (2014).
Summary: In this paper, we consider the edge fault tolerance of the \(n\)-dimensional burnt pancake graph \(\mathrm{BP}_n\) such that each vertex is incident with at least two fault free edges. Based on this requirement, we show that \(\mathrm{BP}_n\) contains a fault free Hamilton cycle even it has up to \(2n-5\) link faults, where \(n\geq 3\).

Cited in 3 Documents

MSC:

05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
05C82 Small world graphs, complex networks (graph-theoretic aspects)
68M15 Reliability, testing and fault tolerance of networks and computer systems
68R10 Graph theory (including graph drawing) in computer science

Keywords:

interconnection network; burnt pancake graph; Hamilton cycle; edge-fault-tolerance; conditional faulty network
Cite Review PDF
Full Text: DOI

References:

[1] Akers, S. B.; Krishnamurthy, B., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 4, 555-566 (1989) · Zbl 0678.94026
[2] Akl, S. G.; Qiu, K.; Stojmenović, I., Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry, Networks, 23, 4, 215-226 (1993) · Zbl 0780.90043
[3] Ashir, Y. A.; Stewart, I. A., Fault-tolerant embedding of Hamiltonian circuits in \(n\)-ary \(n\)-cubes, SIAM J. Discrete Math., 15, 3, 317-328 (2002) · Zbl 1018.68058
[4] Bondy, J. A.; Murty, U. S.R., Graph Theory (2007), Springer: Springer New York · Zbl 1134.05001
[5] Chin, C.; Weng, T. H.; Hsu, L. H.; Chiou, S. C., The spanning connectivity of the burnt pancake graphs, IEICE Trans. Inf. Syst., E92-D, 3, 389-400 (2009)
[6] Cohen, D. S.; Blum, M., On the problem of sorting burnt pancakes, Discrete Appl. Math., 61, 2, 105-120 (1995) · Zbl 0831.68029
[7] Fu, J. S., Conditional fault-tolerant Hamiltonicity of star graphs, Parallel Comput., 33, 488-496 (2007)
[9] Garfgano, L.; Vaccaro, U.; Vozella, A., Fault tolerant routing in the star and pancake interconnection networks, Inform. Process. Lett., 45, 6, 315-320 (1993) · Zbl 0777.68026
[10] Gates, W. H.; Papadimitriou, C. H., Bounds for sorting by prefix reversal, Discrete Math., 27, 47-57 (1979) · Zbl 0397.68062
[11] Heydari, M.; Sudborough, I. H., On sorting by prefix reversals and the diameter of pancake networks, Lecture Notes in Comput. Sci., 678, 218-227 (1993)
[12] Hsieh, S. Y.; Wu, C. Y., Edge-fault-tolerant Hamiltonicity of locally twisted cubes under conditional edge faults, J. Comb. Optim., 19, 1, 16-30 (2010) · Zbl 1185.90029
[13] Hu, X. L.; Liu, H. Q., The (conditional) matching preclusion for burnt pancake graphs, Discrete Appl. Math., 161, 1481-1489 (2013) · Zbl 1287.05117
[14] Hung, H. S.; Fu, J. S.; Chen, G. H., Fault free Hamilton cycles in crossed cubes with conditional link faults, Inform. Sci., 177, 24, 5664-5674 (2007) · Zbl 1132.68018
[15] Iwasawa, N.; Watanabe, T.; Iwasaki, T., Cluster-fault-tolerant routing in burnt pancake graphs, Algorithms Archit. Parallel Process. Lecture Notes in Comput Sci., 6082, 264-274 (2010)
[16] Kaneko, K., An algorithm for node-to-Set disjoint paths problem in burnt pancake graphs, IEICE Trans. Inf. Syst., E86-D, 12, 2588-2594 (2003)
[17] Kaneko, K., Hamilton cycles and Hamilton paths in faulty burnt pancake graphs, IEICE Trans. Inf. Syst., E90-D, 4, 716-721 (2007)
[18] Lai, Y. L.; Yu, D. C., Mutually independent Hamilton cycle of burnt pancake graphs, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E94-A, 7, 1553-1557 (2011)
[19] Tatsuya, I.; Kaneko, K., Fault-tolerant routing in burnt pancake graphs, Inform. Process. Lett., 110, 535-538 (2010) · Zbl 1234.68325
[21] Tsai, P. Y.; Fu, J. S.; Chen, G. H., Edge-fault-tolerant Hamiltonicity of pancake graphs under the conditional fault model, Theoret. Comput. Sci., 409, 450-460 (2008) · Zbl 1155.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.