Multicompetition Numbers of Some Multigraphs

Abstract

In \(1990\), Anderson et al. \([1]\) generalized the competition graph of a digraph to the competition multigraph of a digraph and defined the multicompetition number of a multigraph. The competition multigraph \(CM(D)\) of a digraph \(D = (V, A)\) is the multigraph \(M = (V, E’)\) where two vertices of \(V\) are joined by \(k\) parallel edges if and only if they have exactly \(\ell\) common preys in \(D\). The multicompetition number \(k^*(M)\) of the multigraph \(M\) is the minimum number \(p\) such that \(M \cup I_p\) is the competition multigraph of an acyclic digraph, where \(I_k\) is a set of \(p\) isolated vertices. In this paper, we study the multicompetition numbers for some multigraphs and generalize some results provided by Kim and Roberts \([9]\), and by Zhao and He \([18]\) on general competition graphs, respectively.