Making a Dominating Set of a Graph Connected

Abstract

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.

Keywords

• independent set
• dominating set
• connected dominating set
• 05c69