The Domination Number of Grids - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles SIAM Journal on Discrete Mathematics Year : 2011

The Domination Number of Grids

Abstract

In this paper, we conclude the calculation of the domination number of all n×m grid graphs. Indeed, we prove Chang's conjecture saying that for every $16 \leq n \leq m, \gamma(G_n,m) = \left\lfloor((n+2)(m+2))/5\right\rfloor - 4.

Keywords

Fichier principal
Vignette du fichier
dg.pdf (166.14 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00569256 , version 1 (24-02-2011)

Identifiers

Cite

Daniel Gonçalves, Alexandre Pinlou, Michaël Rao, Stéphan Thomassé. The Domination Number of Grids. SIAM Journal on Discrete Mathematics, 2011, 25, pp.1443-1453. ⟨10.1137/11082574⟩. ⟨lirmm-00569256⟩
194 View
1394 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More