Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl

PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
• Artykuł - szczegóły

Open Mathematics

2010 | 8 | 6 | 1048-1057

The signed k-domination number of directed graphs

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.

EN

1048-1057

wydano
2010-12-01
online
2010-10-30

Twórcy

autor
• Azarbaijan University of Tarbiat Moallem
• Azarbaijan University of Tarbiat Moallem
autor
• Islamic Azad University, Branches of Heris
autor
• RWTH-Aachen University

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