On the diameter of domination bicritical graphs
Michitaka Furuya · Australas. J Comb. · 2015
For a graph G ,w e letγ(G) denote the domination number of G. A graph G is said to be k-bicritical if γ(G )= k and γ(G −{ x, y}) <k for any two vertices x, y ∈ V (G). Brigham et al. [Discrete Math. 305 (2005), 18–32] conjectured that the diameter of a connected k-bicritical graph is at most k − 1. However, in [Australas. J. Combin. 53 (2012), 53–65], counterexamples of the conjecture for k � 4 were constructed by this author. In this paper, we construct counterexamples of the conjecture for k =4 . Our main aim is to give upper bounds of the diameter of a bicritical graph. In particular, we show that the diameter of a connected k-bicritical graph is at most 2k − 3.