A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS

Abstract

Let α 2 (G), γ(G) and γ c (G) be the 2-independence number, the domination number, and the connected domination number of a graph G respectively. Then α 2 (G) ≤ γ (G) ≤ γ c (G). In this paper , we present a simple heuristic for Minimum Connected Dominating Set in graphs. When running on a graph G excluding K m (the complete graph of order m) as a minor, the heuristic produces a connected dominating set of cardinality at most 7α 2 (G) - 4 if m = 3, or at most [Formula: see text] if m ≥ 4. In particular, if running on a planar graph G, the heuristic outputs a connected dominating set of cardinality at most 15α 2 (G) - 5.