کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418409 | 681664 | 2012 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Competition numbers of complete rr-partite graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 160, Issue 15, October 2012, Pages 2271–2276
نویسندگان
Bo-Jr Li, Gerard J. Chang,