A note on k-Roman graphs

• Autorzy: Bouchou A. , Blidia M. , Chellali M.
• Języki publikacji: EN

Abstrakty

EN

Let G = (V,E) be a graph and let k be a positive integer. A subset D of V (G) is a k-dominating set of G if every vertex in V (G) \D has at least k neighbours in D. The k-domination number Υk(G) is the minimum cardinality of a k-dominating set of G. A Roman k-dominating function on G is a function f : V (G) →{0, 1, 2} such that every vertex u for which f(u) = 0 is adjacent to at least k vertices v1, v2, . . . , vk with f(vi) = 2 for i = 1, 2, . . . , k. The weight of a Roman k-dominating function is the value [formula] and the minimum weight of a Roman k-dominating function on G is called the Roman k-domination number Υk(G) of G. A graph G is said to be a k-Roman graph if ΥkR(G) = 2Υk(G) . In this note we study k-Roman graphs.

Słowa kluczowe

EN

Roman k-domination; k-Roman graph

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2013
• Tom: Vol. 33, no. 4
• Strony: 641--646
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Bouchou A.

• University Dr Yahia Farès Médéa, Algeria

autor

Blidia M.

• University of Blida LAMDA-RO, Department of Mathematics B.P. 270, Blida, Algeria

autor

Chellali M.

• University of Blida LAMDA-RO, Department of Mathematics B.P. 270, Blida, Algeria

Bibliografia

• [1] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi, Roman domination in graphs, Discrete Mathematics 278 (2004), 11–22.
• [2] J.F. Fink, M.S. Jacobson, n-domination in graphs, Graph Theory with Applications to Algorithms and Computer Science, John Wiley and Sons, New York 1985, 282–300.
• [3] K. Kämmerling, L. Volkmann, Roman k-domination in graphs, J. Korean Math. Soc. 46 (2009), 1309–1318.
• [4] C.S. ReVelle, K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer Math. Monthly 107 (2000), 585–594.
• [5] I. Steward, Defend the Roman Empire!, Sci. Amer. 281 (1999), 136–139.
• [6] L. Volkmann, Some remarks on lower bounds on the p-domination number in trees, J. Combin. Math. Combin. Comput. 61 (2007), 159–167.
• [7] L. Volkmann, Graphen an allen Ecken und Kanten, RWTH Aachen 2006, XVI, 377 pp.