Connected triangle-free \(m\)-step competition graphs (Q1765515): Difference between revisions

Let \(D\) be a digraph, where from an ecological perspective \(D\) is a food web in which each vertex represents an organism and each arc represents a predator-prey relationship. Specifically, if \(x\) and \(u\) are vertices (organisms) in \(D\) and \(u\) is a prey of \(x\), then \(D\) ontains the arc \((x,u)\). If vertices \(x\) and \(y\) have a common prey, then they are in competition. The competition graph of \(D\), denoted by \(C(D)\), has the same vertex set as \(D\), and there is an edge between vertices \(x\) and \(y\) in \(C(D)\) when \(x\) and \(y\) are in competition in \(D\). And with that a directed walk of length \(k\) from a vertex \(v\) to a vertex \(w\) in a digraph consists of a sequence of vertices \((v_0,v_1,\dots, v_{k-1}, v_k)\), where \(v= v_0\) and \(w= v_k\), such that \((v_i, v_{i+1})\) is an arc in the digraph for each \(i\), \(0\leq i< k\); both vertices and arcs may occur multiple times in a directed walk. The \(m\)-step competition graph, which is a generalization of the competition graph, can be introduced in the following manner. Given a digraph \(D\), possibly containing loops, and some positive integer \(m\), we say that a vertex \(u\) is an \(m\)-step prey of a vertex \(x\) if there is a directed walk of length \(m\) from \(x\) to \(u\) in \(D\). Furthermore, \(u\) is an \(m\)-common prey of vertices \(x\) and \(y\) if \(u\) is an \(m\)-step prey of both \(x\) and \(y\). The \(m\)-step digraph \(D^m\) has the same vertex set as \(D\), and \((x,u)\) is an arc in \(D^m\) if \(u\) is an \(m\)-step prey of \(x\). The \(m\)-step competition graph of a digraph \(D\), denoted \(C^m(D)\), is defined to be \(C^m(D)= C(D^m)\); that means there is an edge between two vertices \(x\) and \(y\) in \(C^m(D)\) if and only if \(x\) and \(y\) have an \(m\)-step common prey in \(D\). (Special case \(m= 1\): \(C^1(D)= C(D)\).) It is already known from the literature that the paths \(P_n\) on \(n\) vertices are easily seen to be 1-step competition graphs for all \(n\); and it is also known that \(P_1\), \(P_2\) and \(P_3\) are \(m\)-step competition graphs for all \(m\). In the present paper the author investigates at first: for what values of \(m\) and \(n\), is \(P_n\) an \(m\)-step competition graph (Section 2); than he is concerned with the much more general question for \(m\geq n\) (Sections 3 and 4). In Section 5 the concept of \(m\)-step number is introduced and an interesting inequality between \(1\)-step and \(m\)-step competition numbers is given. In summary: -- For \(n\geq 2\), the path \(P_n\) is an \((n-1)\)-step competition graph (Theorem 1), and for \(n\geq 2\), the path \(P_n\) is an \((n-2)\)-step competition graph (Theorem 2). -- For positive integers \(m\geq n\), the only connected triangle-free \(m\)-step competition graph on \(n\) vertices is the star graph \(S_{n-1}\) (Theorem 3, main result). -- Corollary of Theorem 3: For every positive integer \(n\), the only connected triangle-free same-step competition graph on \(n\) vertices is \(S_{n-1}\) (Corollary 11). -- Definition 12: Given a graph \(G\) and a positive integer \(m\), the \(m\)-step competition number \(k^{(m)}(G)\) of \(G\) is the smallest number \(k\) such that \(G\) together with \(k\) isovertices is the \(m\)-step competition graph of an acyclic digraph. -- The author gets the following inequality between \(1\)-step and \(m\)-step competition numbers: \(k(G)\leq k^{(m)}(G)- m+ 1\) (Theorem 13).