کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420191 | 683902 | 2012 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study the linear clique-width of graphs that are obtained from paths by disjoint union and adding true twins. We show that these graphs have linear clique-width at most 4, and we give a complete characterisation of their linear clique-width by forbidden induced subgraphs. As a consequence, we obtain a linear-time algorithm for computing the linear clique-width of the considered graphs. Our results extend the previously known set of forbidden induced subgraphs for graphs of linear clique-width at most 3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issue 6, April 2012, Pages 888–901
Journal: Discrete Applied Mathematics - Volume 160, Issue 6, April 2012, Pages 888–901
نویسندگان
Pinar Heggernes, Daniel Meister, Charis Papadopoulos,