Fault-free Hamilton cycles in burnt pancake graphs with conditional edge faults. (English) Zbl 1288.05147
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\).
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 networkReferences:
[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.