کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420105 683895 2011 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On graphs without a C4C4 or a diamond
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On graphs without a C4C4 or a diamond
چکیده انگلیسی

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
نویسندگان
, , , ,