2021/09/29 by Masahisa Goto, Goto, Masahisa, Koji Kobayashi +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2109.14108
openalex publication_date 2021/09/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given an undirected simple graph, a subset of the vertices of the graph is a \em 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 \em 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 \em connected domination number, of an m × n grid graph for any m and n.