Distance domination and linear-vizing constants

Abstract

Generalizing and strengthening a classical result of Vizing, Rautenbach proved a linear relationship between the domination number, the maximum degree, the number of vertices, and the number of edges for graphs with no isolated vertices. The sharpest version of this result was established recently by Henning and the first author. In their paper, the question was raised of establishing the sharpest possible linear-Vizing inequality for other domination parameters; finding the minimum so that for every graph G and a domination parameter γ′. In particular, the question was raised of showing that a key portion of the inequality – the linear-Vizing constant – remained bounded when γ′ was distance-2 domination. In this note, we settle this question in the affirmative. The key ingredient arises from a simple new proof of a result of Henning and Lichiardopol bounding the distance-k domination number.