کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418803 | 681720 | 2009 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The competition number of a graph with exactly hh holes, all of which are independent
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given an acyclic digraph DD, the competition graph C(D)C(D) of DD is the graph with the same vertex set as DD where 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 least number of isolated vertices that must be added to GG to form a competition graph. The purpose of this paper is to prove that the competition number of a graph with exactly hh holes, all of which are independent, is at most h+1h+1. This generalizes the result for h=0h=0 given by Roberts, and the result for h=1h=1 given by Cho and Kim.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 7, 6 April 2009, Pages 1337–1341
Journal: Discrete Applied Mathematics - Volume 157, Issue 7, 6 April 2009, Pages 1337–1341
نویسندگان
Bo-Jr Li, Gerard J. Chang,