On niche graphs of bipartite tournaments

Abstract

Let D be a digraph. The niche graph of D has the same set of vertices as D and an edge between vertices u and v if and only if there exists a common in-neighbor or a ommon out-neighbor of u and v in D. Kim et al. [The competition graphs of oriented complete bipartite graphs, Discrete Applied Mathematics 201 (2016) 182–190] studied the competition graphs of bipartite tournaments. In this thesis, we study the niche graphs of bipartite tournaments to extend their results. We characterize graphs that can be represented as the niche graphs of bipartite tournaments. Then we present forbidden induced subgraphs for niche graphs of bipartite tournaments. We also study niche graphs of strongly connected bipartite tournaments. Finally, we consider the extremal cases of niche graphs of bipartite tournaments each of which has the maximum number of edges or the minimum number of edges.