کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435192 | 689879 | 2016 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Proper orientation of cacti
ترجمه فارسی عنوان
جهت گیری مناسب کاکتوس ها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
جهت گیری مناسب؛ رنگ آمیزی نمودار؛ نمودار کاکتوس؛ نمودار بدون چنگال؛ نمودار مسطح؛ نمودار بلوک
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
An orientation of a graph G is proper if two adjacent vertices have different in-degrees. The proper-orientation number χ→(G) of a graph G is the minimum maximum in-degree of a proper orientation of G.In [1], the authors ask whether the proper orientation number of a planar graph is bounded.We prove that every cactus admits a proper orientation with maximum in-degree at most 7. We also prove that the bound 7 is tight by showing a cactus having no proper orientation with maximum in-degree less than 7. We also prove that any planar claw-free graph has a proper orientation with maximum in-degree at most 6 and that this bound can also be attained.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 639, 1 August 2016, Pages 14–25
Journal: Theoretical Computer Science - Volume 639, 1 August 2016, Pages 14–25
نویسندگان
Julio Araujo, Frédéric Havet, Claudia Linhares Sales, Ana Silva,