Connected domination in grid graphs
share
Given an undirected simple graph, a subset of the vertices of the graph is a dominating set if every vertex not in the subset is adjacent to at least one vertex in the subset. A subset of the vertices of the graph is a connected dominating set if the subset is a dominating set and the subgraph induced by the subset is connected. In this paper, we determine the minimum cardinality of a connected dominating set, called the connected domination number, of an m × n grid graph for any m and n.
READ FULL TEXT