کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418858 | 681722 | 2015 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Cycles in complementary prisms
ترجمه فارسی عنوان
چرخه در منشا مکمل
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
منشور تکمیلی، منشور همیلتون شگفت انگیز
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The complementary prism GG¯ of a graph GG arises from the disjoint union of GG and the complement G¯ of GG by adding a perfect matching joining corresponding pairs of vertices in GG and G¯. Partially answering a question posed by Haynes et al. (2007) we provide an efficient characterization of the circumference of the complementary prism TT¯ of a tree TT and show that TT¯ has cycles of all lengths between 3 and its circumference. Furthermore, we prove that for a given graph of bounded maximum degree it can be decided in polynomial time whether its complementary prism is Hamiltonian.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 193, 1 October 2015, Pages 180–186
Journal: Discrete Applied Mathematics - Volume 193, 1 October 2015, Pages 180–186
نویسندگان
Dirk Meierling, Fábio Protti, Dieter Rautenbach, Aline Ribeiro de Almeida,