کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419235 683758 2016 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Clique-width of path powers
ترجمه فارسی عنوان
عرض دسته قدرت مسیر
کلمات کلیدی
عرض دسته ؛ نمودار فاصله مناسب؛ محاسبات خطی؛ خصوصیات زیرگرافی ناشی از ممنوعیت
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We describe the clique-width of path powers by an exact formula, depending only on the number of vertices and the clique number. As a consequence, the clique-width of path powers can be computed in linear time. Path powers are a graph class of unbounded clique-width. Prior to our result, square grids constituted the only known graph class of unbounded clique-width with a similar result. We also show that clique-width and linear clique-width coincide on path powers.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 205, 31 May 2016, Pages 62–72
نویسندگان
, , , ,