The diameter of domination k‐critical graphs
Odile Favaron, David P. Sumner, Ewa Wojcicka · Journal of Graph Theory · 1994
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 2k − 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.