On the connectivity of generalized \(p\)-cycles. (Q2716018)

The paper studies generalized \(p\)-cycles. A generalized \(p\)-cycle is a digraph whose set of vertices is partitionable into \(p\) parts that are cyclically ordered in such a way that the vertices in one part are adjacent only to vertices in the next part. A numerical invariant \(\ell (G)\) of a digraph \(G\) is defined so that if \(D\) is the diameter of \(G\), then \(1\leq \ell \leq D\) and if \(d(x,y)\leq \ell \), the shortest \(x\rightarrow y\) path is unique and there are no \(x\rightarrow y\) paths of length \(d(x,y) + 1\) and if \(d(x,y) = \ell \), then there is only one shortest \(x\rightarrow y\) path. The number \(\ell (G)\) is related to the diameter, the minimum degree and connectivity of \(G\) in digraphs in general and in generalized \(p\)-cycles in particular.