Saturated domino coverings (Q2786919)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Saturated domino coverings |
scientific article; zbMATH DE number 6544925
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Saturated domino coverings |
scientific article; zbMATH DE number 6544925 |
Statements
23 February 2016
0 references
dominating set
0 references
edge cover
0 references
grid graph
0 references
polyomino
0 references
math.CO
0 references
Saturated domino coverings (English)
0 references
The problem of finding the maximum size of a minimal edge cover of a grid graph \(G\) is considered. It is not difficult to show that this size is equal to \(|V(G)|-\gamma(G)\), where \(\gamma(G)\) is the domination number of \(G\). The problem is then settled as \textit{D. Gonçalves} et al. [SIAM J. Discrete Math. 25, No. 3, 1443--1453 (2011; Zbl 1237.05150)] completed the work on determining \(\gamma(G)\) for grid graphs. Tilings by polyominoes play a central role in the paper, where also some other graphs than grid graphs are discussed.
0 references
