کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419932 | 683877 | 2013 | 7 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Applied Mathematics - Volume 161, Issues 16–17, November 2013, Pages 2420–2426