کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649463 1342457 2009 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the computation of the hull number of a graph
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the computation of the hull number of a graph
چکیده انگلیسی

Let GG be a graph. If u,v∈V(G)u,v∈V(G), a u–vu–vshortest path   of GG is a path linking uu and vv with minimum number of edges. The closed interval   I[u,v]I[u,v] consists of all vertices lying in some u–vu–v shortest path of GG. For S⊆V(G)S⊆V(G), the set I[S]I[S] is the union of all sets I[u,v]I[u,v] for u,v∈Su,v∈S. We say that SS is a convex set   if I[S]=SI[S]=S. The convex hull   of SS, denoted Ih[S]Ih[S], is the smallest convex set containing SS. A set SS is a hull set   of GG if Ih[S]=V(G)Ih[S]=V(G). The cardinality of a minimum hull set of GG is the hull number   of GG, denoted by hn(G)hn(G). In this work we prove that deciding whether hn(G)≤khn(G)≤k is NP-complete.We also present polynomial-time algorithms for computing hn(G)hn(G) when GG is a unit interval graph, a cograph or a split graph.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 18, 28 September 2009, Pages 5668–5674
نویسندگان
, , , , ,