The signed k-domination number of directed graphs

• Autorzy: Maryam Atapour , Seyyed Sheikholeslami , Rana Hajypory , Lutz Volkmann
• 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.

Słowa kluczowe

EN

Signed k-dominating function; Signed k-domination number; Directed graph

Kategorie tematyczne

• 05C45: Eulerian and Hamiltonian graphs
• 05C20: Directed graphs (digraphs), tournaments
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2010
• Tom: 8
• Numer: 6
• Strony: 1048-1057

Daty

wydano

2010-12-01

online

2010-10-30

Twórcy

autor

Maryam Atapour

• Azarbaijan University of Tarbiat Moallem

autor

Seyyed Sheikholeslami

• Azarbaijan University of Tarbiat Moallem

autor

Rana Hajypory

• Islamic Azad University, Branches of Heris

autor

Lutz Volkmann

• 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

Identyfikatory

DOI

10.2478/s11533-010-0077-5