Pancyclicity of \(k\)-ary \(n\)-cube networks with faulty vertices and edges (Q765363)

Thanks to constant technological progress, multiprocessor systems with ever increasing number of interconnected computing nodes are becoming a reality. It is unavoidable that some of those nodes will fail, thus disrupting system performance. As a result, it becomes crucial to study a whole range of fault-tolerance properties of interconnection networks. A graph \(G\) is said to be \(f\)-fault \(p\)-pancyclic if, after removing a subgraph \(F \subseteq V(G) \cup E(G)\), \(|F|\leq f\), from \(G\), the remaining subgraph \(G-F\) contains a cycle of every length from \(p\) to \(|V(G-F)|\). This measurement plays a vital role for the determination whether an interconnection network is suitable for an application when mapping cycles of any length into this network is necessary. This paper shows that the popular \(k\)-ary \(n\)-cubes is \((2n-2)\)-fault \(k\)-pancyclic for \(n\geq 2\) and odd \(k \geq 3\) through a detailed analysis by cases. The restriction on \(k\) being odd is needed since, when \(k\) is even, a \(k\)-ary \(n\)-cube is bipartite, thus cannot be pancyclic. As cycles \(C_k\), the 2-dimensional square torus \(T_k\), and the hypercube \(Q_n\) are all special cases of \(k\)-ary \(n\)-cubes; when taking \(n\) to be 1, 2, and \(k\) to be 2, respectively, this result immediately solves the same problem for the aforementioned structures.