Characterizing paths as \(m\)-step competition graphs (Q708427)

Let \(D\) be a digraph and \(x\) be a vertex of \(D\). Then \(N_{m}(x)\) denotes the set of all vertices \(y\) of \(D\) such that there is an \(m\)-step walk from \(x\) to \(y\). Two vertices \(x\) and \(y\) of \(D\) are said to be in \(m\)-step competition if \(N_{m}(x)\cap N_{m}(y)\neq \varnothing \). The \(m\)-step competition of \(D\) is the simple graph \(C^{m}(D)\) in which the vertex set is the same vertex set as \(D\) and \(xy\) is an edge if and only if \(x\) and \(y\) are in \(m\)-step competition in \(D\). \textit{H. H. Cho}, \textit{S.-R. Ki,}, and \textit{Y. Nam} [``The \(m\)-step competition graph of a digraph,'' Discrete Appl. Math. 105, No.\,1-3, 115--127 (2000; Zbl 0966.05066)] proved that \(P_{n}\), the path on \(n\) vertices, is a \(2\)-step competition graph. \textit{G. T. Helleloid} [''Connected triangle-free \(m\)-step competition graphs,'' Discrete Appl. Math. 145, No.\,3, 376--383 (2005; Zbl 1066.05120)] proved that \(P_{n}\) is an \((n-1)\)- and \((n-2)\)-step competition graph and that \(P_{n}\) is an \(m\)-step competition graph for \(m \geq n>3\). This paper is a continuation of the above works in which the authors proved that if \(m\) divides \(n-1\) or \(n-2\), then \(P_{n}\) is an \(m\)-step competition graph and that if \(n \geq 6\) and \(\frac{n}{2} \leq m \leq n-3\), then \(P_{n}\) is not an \(m\)-step competition graph.