کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418409 681664 2012 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Competition numbers of complete rr-partite graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Competition numbers of complete rr-partite graphs
چکیده انگلیسی

The competition graph C(D)C(D) of an acyclic digraph DD is the graph with the same vertex set as DD and two distinct vertices xx and yy are adjacent in C(D)C(D) if and only if there is a vertex vv in DD such that (x,v)(x,v) and (y,v)(y,v) are arcs of DD. The competition number κ(G)κ(G) of a graph GG is the minimum number of isolated vertices that must be added to GG to form the competition graph of an acyclic digraph. In this paper, we investigate competition numbers of complete rr-partite graphs Kn1,n2,…,nrKn1,n2,…,nr. In particular, we determine the numbers for r=3r=3 and for some cases of r≥4r≥4. We also give bounds for the competition numbers of general complete rr-partite graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issue 15, October 2012, Pages 2271–2276
نویسندگان
, ,