کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420302 | 683920 | 2010 | 5 صفحه PDF | دانلود رایگان |
Let DD be an acyclic digraph. The competition graph of DD is a graph which has the same vertex set as DD and has an edge between uu and vv if and only if there exists a vertex xx in DD such that (u,x)(u,x) and (v,x)(v,x) are arcs of DD. For any graph GG, GG together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G)k(G) of GG is the smallest number of such isolated vertices.A hole of a graph is an induced cycle of length at least four. Kim (2005) [8] conjectured that the competition number of a graph with hh holes is at most h+1h+1. Recently, Li and Chang (2009) [11] showed that the conjecture is true when the holes are independent. In this paper, we show that the conjecture is true though the holes are not independent but mutually edge-disjoint.
Journal: Discrete Applied Mathematics - Volume 158, Issue 13, 6 July 2010, Pages 1456–1460