کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420105 | 683895 | 2011 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On graphs without a C4C4 or a diamond
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider the class of (C4C4, diamond)-free graphs; graphs in this class do not contain a C4C4 or a diamond as an induced subgraph. We provide an efficient recognition algorithm for this class. We count the number of maximal cliques in a (C4C4, diamond)-free graph and the number of nn-vertex, labeled (C4C4, diamond)-free graphs. We also give an efficient algorithm for finding a largest clique in the more general class of (house, diamond)-free graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 7, 6 April 2011, Pages 581–587
Journal: Discrete Applied Mathematics - Volume 159, Issue 7, 6 April 2011, Pages 581–587
نویسندگان
Elaine M. Eschen, Chính T. Hoàng, Jeremy P. Spinrad, R. Sritharan,