Number of Dominating Sets in Cylindric Square Grid Graphs

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

A dominating set of a graph is a subset D of the vertices such that every vertex not in D is adjacent to some vertex of D. In this paper, we introduce several variants of dominating sets in the square grid, periodic square grid and cylindric square grid by considering translation symmetry. We provide their exact enumerations in terms of domination polynomials. We also analyze the asymptotic behavior of the growth rates of their cardinality.

Original languageEnglish
Pages (from-to)1357-1372
Number of pages16
JournalGraphs and Combinatorics
Volume37
Issue number4
DOIs
Publication statusPublished - 2021 Jul

Keywords

  • Cylindric square grid
  • Dominating set
  • Domination polynomial

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Number of Dominating Sets in Cylindric Square Grid Graphs'. Together they form a unique fingerprint.

Cite this