PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2010 | 8 | 6 | 1048-1057
Tytuł artykułu

The signed k-domination number of directed graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Let k ≥ 1 be an integer, and let D = (V; A) be a finite simple digraph, for which d D− ≥ k − 1 for all v ɛ V. A function f: V → {−1; 1} is called a signed k-dominating function (SkDF) if f(N −[v]) ≥ k for each vertex v ɛ V. The weight w(f) of f is defined by $$ \sum\nolimits_{v \in V} {f(v)} $$. The signed k-domination number for a digraph D is γkS(D) = min {w(f|f) is an SkDF of D. In this paper, we initiate the study of signed k-domination in digraphs. In particular, we present some sharp lower bounds for γkS(D) in terms of the order, the maximum and minimum outdegree and indegree, and the chromatic number. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs and digraphs.
Wydawca
Czasopismo
Rocznik
Tom
8
Numer
6
Strony
1048-1057
Opis fizyczny
Daty
wydano
2010-12-01
online
2010-10-30
Twórcy
  • Azarbaijan University of Tarbiat Moallem
Bibliografia
  • [1] Dunbar J.E., Hedetniemi S.T., Henning M.A., Slater P.J., Signed domination in graphs, In: Graph Theory, Combinatorics, and Algorithms, 1, Kalamazoo, 1992, Wiley-Intersci. Publ., Wiley, New York, 1995, 311–321
  • [2] Henning M.A., Slater P.J., Inequalities relating domination parameters in cubic graphs, Discrete Math., 1996, 158(1–3), 87–98 http://dx.doi.org/10.1016/0012-365X(96)00025-8
  • [3] Karami H., Sheikholeslami S.M., Khodkar A., Lower bounds on the signed domination numbers of directed graphs, Discrete Math., 2009, 309(8), 2567–2570 http://dx.doi.org/10.1016/j.disc.2008.04.001
  • [4] Szekeres G., Wilf H.S., An inequality for the chromatic number of a graph, J. Combin. Theory, 1968, 4, 1–3 http://dx.doi.org/10.1016/S0021-9800(68)80081-X
  • [5] Wang C.P., The signed k-domination numbers in graphs, Ars Combin. (in press)
  • [6] West D.B., Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River, 2000
  • [7] Zelinka B., Signed domination numbers of directed graphs, Czechoslovak Math. J., 2005, 55(130)(2), 479–482 http://dx.doi.org/10.1007/s10587-005-0038-5
  • [8] Zhang Z., Xu B., Li Y., Liu L., A note on the lower bounds of signed domination number of a graph, Discrete Math., 1999, 195(1–3), 295–298 http://dx.doi.org/10.1016/S0012-365X(98)00189-7
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_2478_s11533-010-0077-5
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.