Some combinatorial aspects of time-stamp systems (Q1209725)

An ordered \(k\)-sequence is a sequence \((y_ 1,\dots,y_ k)\) of vertices of an oriented graph \(G\) such that if \(1\leq i<j\leq k\) then the arc \((y_ i,y_ j)\) is in \(G\). An oriented graph \(G\) is a \(p\)-restricted time- stamp system of order \(k\) if there exists a family \({\mathcal F}\) of ordered \(k\)-sequences of vertices of \(G\) such that (a) every vertex of \(G\) belongs to some element of \({\mathcal F}\), and (b) if \((u_ 1,\dots,u_ k)\) is an element of \({\mathcal F}\) and \(i\leq p\) then there is a vertex \(v\) such that \((u_ 1,\dots,u_{i-1},u_{i+1},\dots,u_ k,v)\) is an element of \({\mathcal F}\). The authors show, among other things, that there exists a \(p\)-restricted time-stamp system of order \(k\) with \(p2^{p-1}(2k-2p+1)\) vertices.