Upper bounds on the diameter of domination dot-critical graphs with given connectivity
The domination number ?(G) ? ( G ) of a graph G G is the minimum cardinality of any dominating set of G G . An edge of a graph is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. In general, every connected graph G G has diameter at most 3?(G)?1 3 ? ( G ) ? 1 . It is known that the diameter of a connected dot-critical graph G G is at most 3?(G)?3 3 ? ( G ) ? 3 . In this paper, we show that, if a dot-critical graph G G has diameter exactly 3?(G)?3 3 ? ( G ) ? 3 , then G G is a path. Furthermore, we focus on dot-critical graphs with high connectivity. We prove that, for l?2 l ? 2 , the diameter of an l l -connected dot-critical graph G G is at most 2?(G)?2 2 ? ( G ) ? 2 , and show that the bound 2?(G)?2 2 ? ( G ) ? 2 is best possible.
diameter dot-critical graph connectivity