A New Lower Bound for the Domination Number of Complete Cylindrical Grid Graphs

2022/07/28 by David R. Guichard, Guichard, David R.
Computer Science · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2207.14414

openalex publication_date 2022/07/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We use a dynamic programming algorithm to establish a lower bound on the domination number of complete grid graphs of the form C_n\square P_m, that is, the Cartesian product of a cycle C_n and a path P_m, for m and n sufficiently large.

Related

• The Domination Number of C_n\square P_m for n≡ 2\pmod5
• Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph
• Total and paired domination numbers of toroidal meshes
• The total bondage number of grid graphs
• The integer \2\-domination number of grids