کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423790 | 1632593 | 2011 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the hull number of some graph classes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the hull number of some graph classes On the hull number of some graph classes](/preview/png/6423790.png)
چکیده انگلیسی
Given a graph G=(V,E), the closed interval of a pair of vertices u,vâV, denoted by I[u,v], is the set of vertices that belongs to some shortest (u,v)-path. For a given SâV, let I[S]=âu,vâSI[u,v]. We say that SâV is a convex set if I[S]=S.The convex hull Ih[S] of a subset SâV is the smallest convex set that contains S. We say that S is a hull set if Ih[S]=V. The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G).We show that deciding if hn(G)⩽k is an NP-complete problem, even if G is bipartite. We also prove that hn(G) can be computed in polynomial time for cactus and P4-sparse graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 49-55
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 49-55
نویسندگان
J. Araujo, V. Campos, F. Giroire, L. Sampaio, R. Soares,