کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871962 | 684128 | 2016 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Graph classes with and without powers of bounded clique-width
ترجمه فارسی عنوان
کلاس های گراف با و بدون قدرت کلاسی عرضی محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کلیدهای عرض، قدرت یک گراف، کلاس گراف ارثی فاصله کانونی کم عرض،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We initiate the study of graph classes of power-bounded clique-width, that is, graph classes for which there exist integers k and â such that the kth powers of the graphs are of clique-width at most â. We give sufficient and necessary conditions for this property. As our main results, we characterize graph classes of power-bounded clique-width within classes defined by either one forbidden induced subgraph, or by two connected forbidden induced subgraphs. We also show that for every positive integer k, there exists a graph class such that the kth powers of graphs in the class form a class of bounded clique-width, while this is not the case for any smaller power.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 199, 30 January 2016, Pages 3-15
Journal: Discrete Applied Mathematics - Volume 199, 30 January 2016, Pages 3-15
نویسندگان
Flavia Bonomo, Luciano N. Grippo, Martin MilaniÄ, MartÃn D. Safe,