کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1708479 | 1012825 | 2011 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Graphs having many holes but with small competition numbers
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
سایر رشته های مهندسی
مکانیک محاسباتی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The competition number k(G) of a graph G is the smallest number k such that G together with k isolated vertices added is the competition graph of an acyclic digraph. A chordless cycle of length at least 4 of a graph is called a hole of the graph. The number of holes of a graph is closely related to its competition number as the competition number of a graph which does not contain a hole is at most one and the competition number of a complete bipartite graph Kân2â,ân2â which has so many holes that no more holes can be added is the largest among those of graphs with n vertices. In this paper, we show that even if a connected graph G has many holes, the competition number of G can be as small as 2 under some assumption. In addition, we show that, for a connected graph G with exactly h holes and at most one non-edge maximal clique, if all the holes of G are pairwise edge-disjoint and the clique number Ï=Ï(G) of G satisfies 2â¤Ïâ¤h+1, then the competition number of G is at most hâÏ+3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics Letters - Volume 24, Issue 8, August 2011, Pages 1331-1335
Journal: Applied Mathematics Letters - Volume 24, Issue 8, August 2011, Pages 1331-1335
نویسندگان
JungYeun Lee, Suh-Ryung Kim, Seog-Jin Kim, Yoshio Sano,