The diameter of domination <i>k</i>‐critical graphs

Abstract

Abstract A graph is k ‐domination‐critical if γ( G) = k , and for any edge e not in G , γ( G + e) = k − 1. In this paper we show that the diameter of a domination k ‐critical graph with k ≧ 2 is at most 2 k − 2. We also show that for every k ≧ 2, there is a k ‐domination‐critical graph having diameter [(3/2) k − 1]. We also show that the diameter of a 4‐domination‐critical graph is at most 5.