کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421260 | 684171 | 2011 | 6 صفحه PDF | دانلود رایگان |
Let GG be a graph with the vertex set V(G)V(G), and let f:V(G)→{−1,1}f:V(G)→{−1,1} be a two-valued function. If GG has no isolated vertices and ∑x∈N(v)f(x)≥1∑x∈N(v)f(x)≥1 for each v∈V(G)v∈V(G), where N(v)N(v) is the neighborhood of vv, then ff is a signed total dominating function on GG. A set {f1,f2,…,fd}{f1,f2,…,fd} of signed total dominating functions on GG with the property that ∑i=1dfi(x)≤1 for each x∈V(G)x∈V(G) is called a signed total dominating family (of functions) on GG. The maximum number of functions in a signed total dominating family on GG is the signed total domatic number of GG, denoted by dtS(G).In this article we mainly present upper bounds on dtS(G), in particular for regular graphs. As an application of these bounds, we show that dtS(G)≤n−3 for any graph GG of order n≥4n≥4 without isolated vertices. Furthermore, we prove the Nordhaus–Gaddum inequality dtS(G)+dtS(G¯)≤n−3 for graphs GG and G¯ of order n≥7n≥7 without isolated vertices, where G¯ is the complement of GG.
Journal: Discrete Applied Mathematics - Volume 159, Issue 8, 28 April 2011, Pages 832–837