Cyclic Niche Graphs and Grids

Abstract

A graph $G=(V,E)$ is a loop niche graph if there is a digraph $D=(V,A)$such that $xy\in E$ iff there exists $z\in V$ such that either $xz$ and $yz\in A$ or $zx$ and $zy\in A$. If $D$ has no loops, $G$ is a cyclic niche graph, and if $D$ is acyclic, $G$ is a niche graph. We give a characterization of triangle-free cyclic niche graphs, and apply this to classify grids.