The competition numbers of complete multipartite graphs with many partite sets

详细信息	查看全文 | 推荐本文 |

• 作者：Suh-Ryung Kim^a ; Boram Park^a ; ^{kawa22@snu.ac.kr} ; ^{borampark22@gmail.com} ; Yoshio Sano^b
• 关键词：Competition graphs ; Competition numbers ; Complete multipartite graphs
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：May, 2012
• 卷：160
• 期：7-8
• 页码：1176-1182
• 文件大小：275 K

摘要

The competition graph of a digraph is a graph which has the same vertex set as and has an edge between two vertices and if and only if there exists a vertex in such that and are arcs of . For any graph , together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number of a graph is defined to be the smallest number of such isolated vertices. In this paper, we study the competition numbers of complete multipartite graphs. We give upper bounds for the competition numbers of complete multipartite graphs with many partite sets, which extends a result given by Park et聽al. (2009)聽. In fact, by using these upper bounds, we compute the exact competition numbers of complete multipartite graphs in which each partite set has two vertices and the competition numbers of complete multipartite graphs in which each partite set has three vertices.