\(p\)-competition numbers (Q689960): Difference between revisions

Let \(D\) denote a digraph whose vertices are species in some ecosystem in which there is an arc from \(x\) to \(y\) if and only if \(x\) preys on \(y\). The \(p\)-competition graph of \(D\) is the graph with the same vertices in which vertices \(u\) and \(v\) are adjacent if and only if \(u\) and \(v\) have at least \(p\) common prey. The \(p\)-competition number \(k_ p(G)\) of a graph \(G\) is the least number of isolated vertices that need to be added to \(G\) so that the resulting graph is the \(p\)-competition graph of some acyclic digraph \(D\). The authors show, among other things, that \(k_ p(G)< k_ 1(G)+ p-1\) and that \(k_ 1(G)-k_ 2(G)\) can be arbitrarily large.