کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777235 | 1632576 | 2016 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the Complexity of the P3-Hull Number of the Cartesian Product of Graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Let G be a finite, simple, and undirected graph and let S be a set of vertices of G. If no vertex of G that does not belong to S has two neighbors in S, then S is P3-convex. The P3-convex hull H(S) of S is the smallest P3-convex set containing S. If H(S)=V(G) we say that S is a P3-hull set of G. The cardinality h(G) of a minimum P3-hull set in G is called the P3-hull number of G. In this paper w extend the result of Centeno et al. [Theoretical Computer Science 412 (2011), 3693-3700] showing that, given a graph G and an integer k, deciding whether h(G)â¤k remains NP-complete for the Cartesian product of graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 55, November 2016, Pages 169-172
Journal: Electronic Notes in Discrete Mathematics - Volume 55, November 2016, Pages 169-172
نویسندگان
Julliano R. Nascimento, Erika M.M. Coelho, Hebert Coelho, Jayme L. Szwarcfiter,