کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419650 | 683846 | 2009 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On cover-structure graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Motivated by a problem in communication complexity, we study cover-structure graphs (cs-graphs), defined as intersection graphs of maximal monochromatic rectangles in a matrix. We show that not every graph is a cs-graph. Especially, squares and odd holes are not cs-graphs.It is natural to look at graphs (beautiful graphs) having the property that each induced subgraph is a cs-graph. They form a new class of Berge graphs. We make progress towards their characterization by showing that every square-free bipartite graph is beautiful, and that beautiful line graphs of square-free bipartite graphs are just Path-or-Even-Cycle-of-Cliques graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 15, 6 August 2009, Pages 3289–3299
Journal: Discrete Applied Mathematics - Volume 157, Issue 15, 6 August 2009, Pages 3289–3299
نویسندگان
Henning Wunderlich,