Upper bounds on the diameter of domination dot-critical graphs with given connectivity

作者：Furuya Michitaka^*

来源：Discrete Applied Mathematics, 2013, 161(16-17): 2420-2426.

DOI：10.1016/j.dam.2013.05.011

• Dot-critical graph
• Diameter
• Connectivity

The domination number gamma(G) of a graph G is the minimum cardinality of any dominating set of 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. %26lt;br%26gt;In general, every connected graph G has diameter at most 3 gamma(G) - 1. It is known that the diameter of a connected dot-critical graph G is at most 3 gamma(G) - 3. In this paper, we show that, if a dot-critical graph G has diameter exactly 3 gamma (G) - 3, then G is a path. Furthermore, we focus on dot-critical graphs with high connectivity. We prove that, for l %26gt;= 2, the diameter of an l-connected dot-critical graph G is at most 2 gamma(G) - 2, and show that the bound 2 gamma(G) - 2 is best possible.

• 出版日期2013-11