Theory and Applications of Graphs (Apr 2020)
On a Vizing-type Integer Domination Conjecture
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šar, Henning, and Klavžar (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 □ H) ≥ γ(G)γ(H). In this note we use the Roman 2-domination number, γ R2 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 □ H) ≥ γ R2(G □ H) ≥ γ(G)γ(H).
Keywords
