کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9512161 1632454 2005 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The competition number of a graph having exactly one hole
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The competition number of a graph having exactly one hole
چکیده انگلیسی
Let D be an acyclic digraph. The competition graph of D has the same set of vertices as D and an edge between vertices u and v if and only if there is a vertex x in D such that (u,x) and (v,x) are arcs of D. The competition number of a graph G, denoted by k(G), is the smallest number k such that G together with k isolated vertices is the competition graph of an acyclic digraph. In this paper, we show that the competition number of a graph having exactly one chordless cycle of length at least 4 is at most two. We also give a large family of such graphs whose competition numbers are less than or equal to one.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 303, Issues 1–3, 6 November 2005, Pages 32-41
نویسندگان
, ,