The niche graph of a digraph \(D\) is the undirected graph defined on the same vertex set in which two vertices are adjacent if they share either a common in-neighbor or a common out-neighbor in \(D\). We define a hierarchy of graphs depending on the condition of being the niche graph of a digraph having, respectively, no cycles, no cycles of length two, no loops, or loops. Our goal is to classify in this hierarchy all graphs of order \(n \geq 3\) having a subgraph isomorphic to \(K_{n-2}\).
Citation
Steve Bowser, Charles Cable. The Niche Category of Dense Graphs[J], Ars Combinatoria, Volume 059. 289-297. .