The \(m\)-step competition graph of a digraph (Q1582072)

The authors define the \(m\)-step competition graph of a digraph and the \(m\)-step competition number \(k^m(G)\) of a graph \(G\) by applying natural generalizations of the well-known concepts of the competition graph of a digraph (\textit{F. S. Roberts} [Lect. Notes Math. 642, 477-490 (1978; Zbl 0389.90036)] and \textit{J. R. Lundgren} [IMA Vol. Math. Appl. 17, 221-243 (1989; Zbl 0701.92023)]) and of the competition number of a graph (\textit{Suh-Ryung Kim} [Ann. Discrete Math. 55, 313-326 (1993; Zbl 0789.05041)]). A characterization of the \(m\)-step competition graphs is obtained. It is shown that any path is a 2-step competition graph of a digraph and any spiked \(n\)-cycle is not the \(m\)-step competition graph of any digraph (for \(n\geq 4\) and \(m\geq 2\)). The 2-step competition numbers of cycles and paths are computed: \(k^2(C_3)=2,\) \(k^2(C_n)=4\) for \(n\geq 4\), and \(k^2(P_n)=2\) for any \(n\geq 2.\) Some open questions are included.