Loop and cyclic niche graphs (Q1805299)

The niche graph of a digraph \(D\) is the graph \(G\) such that an edge \((x, y)\) is in \(G\) if and only if there is a node \(z\) in \(D\) so that either \((x, z)\) and \((y, z)\) or \((z, x)\) and \((z, y)\) are arcs of \(D\). The problem of which graphs were the niche graph of acyclic digraphs have received much attention. The paper considers the effect of relaxing the requirement that the digraph be acyclic. Several new classes of graphs are found to be niche graphs, but many graphs still are neither niche graphs, nor can they be made into niche graphs by adding isolated nodes.