Theory and Applications of Graphs Theory and Applications of Graphs

Abstract

Given a simple graph G , a dominating set in G is a set of vertices S such that every vertex not in S has a neighbor in S . Denote the domination number, which is the size of any minimum dominating set of G , by γ ( G ). For any integer k ≥ 1, a function f : V ( G ) → { 0 , 1 , ..., k } is called a { k } -dominating function if the sum of its function values over any closed neighborhood is at least k . The weight of a { k } -dominating function is the sum of its values over all the vertices. The { k } -domination number of G , γ { k } ( G ), is defined to be the minimum weight taken over all { k } -domination functions. Breˇsar, Henning, and Klavˇzar (On integer domination in graphs and Vizing-like problems. Taiwanese J. Math. 10(5) (2006) pp. 1317–1328) asked whether there exists an integer k ≥ 2 so that γ { k } ( G (cid:50) H ) ≥ γ ( G ) γ ( H ). In this note we use the Roman { 2 } - domination number, γ R 2 of Chellali, Haynes, Hedetniemi, and McRae, (Roman { 2 } -domination. Discrete Applied Mathematics 204 (2016) pp. 22-28.) to prove that if G is a claw-free graph and H is an arbitrary graph, then γ { 2 } ( G (cid:50) H ) ≥ γ R 2 ( G (cid:50) H ) ≥ γ ( G ) γ ( H ), which also implies the conjecture for all k ≥ 2.