Indexed by:
Abstract:
The pancake graph is an interconnection network that plays a vital role in designing parallel and distributed systems. Due to the unavoidable occurrence of edge faults in large-scale networks and the wide application of path and cycle structures, it is essential and practical to explore the embedding of Hamiltonian paths and cycles in faulty networks. However, existing fault models ignore practical distributions of faulty edges so that only linear edge faults can be tolerated. This paper introduces a powerful fault model named the partitioned fault model. Based on this model, we study the existence of Hamiltonian paths and cycles on pancake graphs with large-scale faulty edges for the first time. We show that the n-dimensional pancake graph Pn admits a Hamiltonian path between any two vertices, avoiding ∑i=4n((i-4)((i-2)!-2)-1)+1 partition-edge faults for 4 ≤ n≤ 7, and avoiding ∑i=8n((i-1)!2-1)+399 faulty partition-edges for n≥ 8. Moreover, we prove that Pn admits a Hamiltonian cycle, avoiding ∑i=4n((i-4)((i-2)!-2)-1)+2 faulty partition-edges for 4 ≤ n≤ 7, and avoiding ∑i=8n((i-1)!2-1)+400 partition-edge faults for n≥ 8. The comparison results show that our results are a large-scale enhancement of existing results. © 2022, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
Keyword:
Reprint 's Address:
Email:
Source :
ISSN: 1865-0929
Year: 2022
Volume: 1723 CCIS
Page: 192-204
Language: English
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1