Multicompetition numbers of some multigraphs

作者：Zhao Yongqiang^*; Chang Gerard J

来源：Ars Combinatoria, 2010, 97: 457-469.

• Competition graph
• Competition number
• Competition multigraph
• Multicompetition number

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 k common preys in D. The multicompetition number k*(M) of the multigraph M is the minimum number p such that M boolean OR I(p) is the competition multigraph of an acyclic digraph, where I(k) is a set of k 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.

• 出版日期2010-10
• 单位石家庄学院