Digraphs whose m-step competition graphs are trees

In this paper, we completely characterize the digraphs of order $n$ whose $m$-step competition graphs are star graphs for positive integers $2\leq m < n$. This result in matrix version identifies the solution set to the matrix equation $X^m(X^T{)}^m={\mathrm{\Lambda }}_n+I_n$ for positive integers $2\le m<n$ where $I_n$ is the identity matrix of order $n$ and ${\mathrm{\Lambda }}_n$ is a $(0,1)$ Boolean matrix such that the first row and the first column consist of $1$’s except $(1,1)$-entry and the remaining entries are $0$, which is the adjacency matrix of a star graph of order $n$. We also derive meaningful properties of the digraphs whose $m$-step competition graphs are trees. In the process, we extend a result of Helleloid~[Connected triangle-free $m$-step competition graphs, Discrete Appl.
Math.\ 145 (2005) 376–383] by showing that for all positive integers $m \geq 2$and$n$,theconnectedtriangle-free$m$-stepcompetitiongraphon$n$ vertices is a tree.