کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435176 | 689877 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the geodetic hull number of Pk-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the geodetic hull number of Pk-free graphs On the geodetic hull number of Pk-free graphs](/preview/png/435176.png)
چکیده انگلیسی
Partially answering a question posed by Araujo, Morel, Sampaio, Soares, and Weber, we show that computing the geodetic hull number of a given P9P9-free graph is NP-hard. Similarly, we show that computing the geodetic interval number of a given P5P5-free graph is NP-hard. Furthermore, we show that the geodetic hull number can be computed in polynomial time for {paw,P5}{paw,P5}-free graphs, triangle-free graphs in which every six vertices induce at most one P5P5, and {C3,…,Ck−2,Pk}{C3,…,Ck−2,Pk}-free graphs for every integer k.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 640, 9 August 2016, Pages 52–60
Journal: Theoretical Computer Science - Volume 640, 9 August 2016, Pages 52–60
نویسندگان
Mitre C. Dourado, Lucia D. Penso, Dieter Rautenbach,