کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650403 1342486 2008 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Variations of Y-dominating functions on graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Variations of Y-dominating functions on graphs
چکیده انگلیسی

Let Y be a subset of real numbers. A Y-dominating function   of a graph G=(V,E)G=(V,E) is a function f:V→Yf:V→Y such that ∑u∈NG[v]f(u)⩾1 for all vertices v∈Vv∈V, where NG[v]={v}∪{u|(u,v)∈E}NG[v]={v}∪{u|(u,v)∈E}. Let f(S)=∑u∈Sf(u) for any subset S of V   and let f(V)f(V) be the weight of f. The Y-domination problem is to find a Y  -dominating function of minimum weight for a graph G=(V,E)G=(V,E). In this paper, we study the variations of Y  -domination such as {k}{k}-domination, k  -tuple domination, signed domination, and minus domination for some classes of graphs. We give formulas to compute the {k}{k}-domination, k-tuple domination, signed domination, and minus domination numbers of paths, cycles, n-fans, n-wheels, n-pans, and n-suns. Besides, we present a unified approach to these four problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. This paper also gives complexity results for the problems on doubly chordal graphs, dually chordal graphs, bipartite planar graphs, chordal bipartite graphs, and planar graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 18, 28 September 2008, Pages 4185–4204
نویسندگان
, ,