Ring embedding in faulty pancake graphs. (English) Zbl 1162.68496
Summary: We consider the fault hamiltonicity and the fault hamiltonian connectivity of the pancake graph \(Pn\). Assume that \(F\subseteq V(P_n) \cup E(P_n)\). For \(n \geqslant 4\), we prove that \(P_n - F\) is hamiltonian if \(|F|\leqslant(n - 3)\) and \(P_n - F\) is hamiltonian connected if \(|F|\leqslant(n - 4)\). Moreover, all the bounds are optimal.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
References:
| [1] | Akers, S. B.; Krishnameurthy, B., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 555-566 (1989) · Zbl 0678.94026 |
| [2] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1980), North-Holland: North-Holland New York · Zbl 1134.05001 |
| [3] | Bouabdallah, A.; Heydemann, M. C.; Opatrný, J.; Sotteau, D., Embedding complete binary trees into star and pancake graphs, Theory Comput. Syst., 279-305 (1998) · Zbl 0896.68108 |
| [4] | Fang, W. C.; Hsu, C. C., On the fault-tolerant embedding of complete binary tree in the pancake graph interconnection network, Inform. Sci., 191-204 (2000) · Zbl 0965.68074 |
| [5] | Gargano, L.; Vaccaro, U.; Vozella, A., Fault tolerant routing in the star and pancake interconnection networks, Inform. Process. Lett., 315-320 (1993) · Zbl 0777.68026 |
| [6] | Gates, W. H.; Papadimitriou, C. H., Bounds for sorting by prefix reversal, Discrete Math., 27, 47-57 (1979) · Zbl 0397.68062 |
| [7] | Heydari, M. H.; Sudborough, I. H., On the diameter of the pancake network, J. Algorithms, 67-94 (1997) · Zbl 0888.68007 |
| [8] | W.T. Huang, J.M. Tan, C.N. Hung, L.H. Hsu, Fault-tolerant hamiltonicity of twisted cubes, to appear in J. Parallel Distributed Comput; W.T. Huang, J.M. Tan, C.N. Hung, L.H. Hsu, Fault-tolerant hamiltonicity of twisted cubes, to appear in J. Parallel Distributed Comput · Zbl 1008.68017 |
| [9] | W.T. Huang, Y.C. Chuang, L.H. Hsu, J.M. Tan, On the fault-tolerant hamiltonicity of crossed cubes, to appear in IEICE Trans. Fundamentals; W.T. Huang, Y.C. Chuang, L.H. Hsu, J.M. Tan, On the fault-tolerant hamiltonicity of crossed cubes, to appear in IEICE Trans. Fundamentals |
| [10] | Kanevsky, A.; Feng, C., On the embedding of cycles in pancake graphs, Parallel Comput., 923-936 (1995) · Zbl 0875.68708 |
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.
