The p-Competition Graphs of Symmetric Digraphs and $p$-Neighborhood Graphs
J. Richard Lundgren, Patricia A. McKenna, Sarah K. Merz, Craig W. Rasmussen · 1995
. The p-competition graph G of a digraph D is a graph on the same vertex set as D, with [x; y] 2 E(G) if and only if jOut(x) " Out(y)j p in D. In this paper we focus on the case in which D is a symmetric digraph ((a; b) is an arc in D if and only if (b; a) is an arc in D). We relate the problem to 2-step graphs, squares, and a generalization of the neighborhood graph called the p-neighborhood graph. We also identify some familiar classes of graphs as 2-competition graphs of loopless symmetric digraphs. I. Introduction. The p-competition graph was introduced in 1989 by Kim, McKee, McMorris, and Roberts [9] as a generalization of the competition graph first presented by Cohen [5] in 1968. The p-competition graph G of a digraph D has an edge between vertices x and y if and only if x and y have at least p common outneighbors in D (i.e. x and y have outarcs to at least p common vertices). We write G = C p (D). See Figure 1 for a digraph and its 2-competition graph. t t t t t t - ? \\Phi...