2019/11/11 by Eoh, Soogang, Choi, Myungho, Kim, Suh-Ryung
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1911.04191
The niche graph of a digraph D has V(D) as the vertex set and an edge uv if and only if (u,w) ∈ A(D) and (v,w) ∈ A(D), or (w,u) ∈ A(D) and (w,v) ∈ A(D) for some w ∈ V(D). The notion of niche graph was introduced by Cable et al. (1989) as a variant of competition graph. If a graph is the niche graph of a digraph D, it is said to be niche-realizable through D. If a graph G is niche-realizable through a k-partite tournament for an integer k ≥ 2, then we say that the pair (G, k) is niche-realizable. Bowser et al. (1999) studied the graphs that are niche-realizable through a tournament and Eoh et al. (2018) studied niche-realizable pairs (G, k) for k=2. In this paper, we study niche-realizable pairs (G, k) when G is a graph and k is an integer at least 3 to extend their work. We show that the niche graph of a k-partite tournament has at most three components if k ≥ 3 and is connected if k ≥ 4. Then we find all the niche-realizable pairs (G, k) when G is a disconnected graph, when G is a complete graph, and when G is a connected triangle-free graph.