Disjoint paths of bounded length in large generalized cycles (Q1292837)

Graphs (both directed and undirected) are used to model interconnection networks. From this viewpoint, the fault diameter of a graph is related to the fault tolerance of the corresponding network. A generalized \(p\)-cycle is a digraph whose vertex set has a partition into \(p\) parts that can be cyclically ordered in such a way that a vertex is adjacent only to vertices belonging to the next part. A lower bound is found for the fault diameter of a generalized \(p\)-cycle. Both the fault diameter and a related parameter (the wide diameter) are also calculated for two extremal families of generalized \(p\)-cycles, namely \(\text{BGC}(p,d,d^p)\) and \(\text{KGC}(p,d,d^{p+ k}+ d^p)\).