Fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity of the folded Petersen cube networks

Abstract

Some research on the folded Petersen cube networks have been published for the past several years due to its favourite properties. In this paper, we consider the fault-tolerant hamiltonicity and the fault-tolerant hamiltonian connectivity of the folded Petersen cube networks. We use FPQ _{n, k} to denote the folded Petersen cube networks of parameters n and k. In this paper, we show that FPQ _{n, k} −F remains hamiltonian for any F ⊆ V(FPQ _{n, k} )∪E(FPQ _{n, k} ) with |F|≤n+3k−2 and FPQ _{n, k} −F remains hamiltonian connected for any F ⊆ V(FPQ _{n, k} )∪E(FPQ _{n, k} ) with |F|≤n+3k−3 if (n, k)∉{(0, 1)}∪{(n, 0) | n is a positive integer}. Moreover, this result is optimal.

Keywords:

• hamiltonian
• hamiltonian connected
• folded Petersen cube networks

2000 AMS Subject Classification :

• 05C45
• 05C75
• 05C85
• 05C90
• 68M10