کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418710 | 681710 | 2010 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An upper bound for the competition numbers of graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A hole of a graph is an induced cycle of length at least 4. Kim (2005) [2] conjectured that the competition number k(G)k(G) is bounded by h(G)+1h(G)+1 for any graph GG, where h(G)h(G) is the number of holes of GG. In Lee et al. [3], it is proved that the conjecture is true for a graph whose holes are mutually edge-disjoint. In Li et al. (2009) [4], it is proved that the conjecture is true for a graph, all of whose holes are independent. In this paper, we prove that Kim’s conjecture is true for a graph GG satisfying the following condition: for each hole CC of GG, there exists an edge which is contained only in CC among all induced cycles of GG.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 2, 28 January 2010, Pages 154–157
Journal: Discrete Applied Mathematics - Volume 158, Issue 2, 28 January 2010, Pages 154–157
نویسندگان
Akira Kamibeppu,