Making a Dominating Set of a Graph Connected

摘要

Let G = ( V,E ) be a graph and S ? V . We say that S is a dominating set of G , if each vertex in V S has a neighbor in S . Moreover, we say that S is a connected (respectively, 2-edge connected or 2-connected) dominating set of G if G [ S ] is connected (respectively, 2-edge connected or 2-connected). The domination (respectively, connected domination, or 2- edge connected domination, or 2-connected domination) number of G is the cardinality of a minimum dominating (respectively, connected dominating, or 2-edge connected dominating, or 2-connected dominating) set of G , and is denoted γ( G ) (respectively γ_(1)( G ), or γ′ _(2)( G ), or γ_(2)( G )). A well-known result of Duchet and Meyniel states that γ_(1)( G ) ≤ 3γ( G ) ? 2 for any connected graph G . We show that if γ( G ) ≥ 2, then γ′ _(2)( G ) ≤ 5γ( G ) ? 4 when G is a 2-edge connected graph and γ_(2)( G ) ≤ 11γ( G ) ? 13 when G is a 2-connected triangle-free graph.