Article ID Journal Published Year Pages File Type
419932 Discrete Applied Mathematics 2013 7 Pages PDF
Abstract

The domination number γ(G)γ(G) of a graph GG is the minimum cardinality of any dominating set of GG. 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 GG has diameter at most 3γ(G)−13γ(G)−1. It is known that the diameter of a connected dot-critical graph GG is at most 3γ(G)−33γ(G)−3. In this paper, we show that, if a dot-critical graph GG has diameter exactly 3γ(G)−33γ(G)−3, then GG is a path. Furthermore, we focus on dot-critical graphs with high connectivity. We prove that, for l≥2l≥2, the diameter of an ll-connected dot-critical graph GG is at most 2γ(G)−22γ(G)−2, and show that the bound 2γ(G)−22γ(G)−2 is best possible.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,