Michaël Rao ; Alexandre Talon - The 2-domination and Roman domination numbers of grid graphs

dmtcs:4952 - Discrete Mathematics & Theoretical Computer Science, May 23, 2019, vol. 21 no. 1, ICGT 2018 - https://doi.org/10.23638/DMTCS-21-1-9
The 2-domination and Roman domination numbers of grid graphs

Authors: Michaël Rao ; Alexandre Talon

    We investigate the 2-domination number for grid graphs, that is the size of a smallest set $D$ of vertices of the grid such that each vertex of the grid belongs to $D$ or has at least two neighbours in $D$. We give a closed formula giving the 2-domination number of any $n \!\times\! m$ grid, hereby confirming the results found by Lu and Xu, and Shaheen et al. for $n \leq 4$ and slightly correct the value of Shaheen et al. for $n = 5$. The proof relies on some dynamic programming algorithms, using transfer matrices in (min,+)-algebra. We also apply the method to solve the Roman domination problem on grid graphs.


    Volume: vol. 21 no. 1, ICGT 2018
    Published on: May 23, 2019
    Accepted on: May 3, 2019
    Submitted on: November 2, 2018
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics

    Linked publications - datasets - softwares

    Source : ScholeXplorer HasVersion DOI 10.48550/arxiv.1810.12896
    • 10.48550/arxiv.1810.12896
    The 2-domination and Roman domination numbers of grid graphs
    Rao, Michaël ; Talon, Alexandre ;

    Consultation statistics

    This page has been seen 588 times.
    This article's PDF has been downloaded 232 times.