On The Trees Whose $2$-Step Compitition Numbers are Two

Abstract

Since Cohen introduced the notion of competition graph in $1968$, various variations have been defined and studied by many authors. Using the combinatorial properties of the adjacency matrices of digraphs, Cho $etal$. $[2]$ introduced the notion of a $m$-step competition graph as a generalization of the notion of a competition graph. Then they $[3]$ computed the $2$-step competition numbers of complete graphs, cycles, and paths. However, it seems difficult to compute the $2$-step competition numbers even for the trees whose competition numbers can easily be computed. Cho $etal$. $[1]$ gave a sufficient condition for a tree to have the $2$-step competition number two. In this paper, we show that this sufficient condition is also a necessary condition for a tree to have the $2$-step competition number two, which completely characterizes the trees whose $2$-step competition numbers are two. In fact, this result turns out to characterize the connected triangle-free graphs whose $2$-step competition numbers are two.