descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Other literature type 01 Jan 2011Embargo end date: 01 Jan 2011 English Publisher:Society for Industrial & Applied Mathematics (SIAM)Journal:SIAM Journal on Discrete Mathematics, volume 25, pages 1,443-1,453 (issn: 0895-4801, eissn: 1095-7146,

Authors: Gonçalves, Daniel; Pinlou, Alexandre; Rao, Michaël; Thomassé, Stéphan;

doi: 10.1137/11082574 , 10.48550/arxiv.1102.5206

arXiv: http://arxiv.org/abs/1102.5206

The Domination Number of Grids

- Summary
- Subjects
- Metrics

Abstract

In this paper, we conclude the calculation of the domination number of all $n\times m$ grid graphs. Indeed, we prove Chang's conjecture saying that for every $16\le n\le m$, $��(G_{n,m})=\lfloor\frac{(n+2)(m+2)}{5}\rfloor -4$.

12 pages, 4 figures

Related Organizations

University of Bordeaux
France
French National Centre for Scientific Research
France
University of Montpellier
France
Université Paul-Valéry Montpellier
France
Montpellier Laboratory of Informatics, Robotics and Microelectronics
France

View all View all

Keywords

FOS: Computer and information sciences, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Discrete Mathematics (cs.DM), grid, domination, Computer Science - Discrete Mathematics

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	73
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%