Metraipolis › archive › dc_eea91d07105f

Upper Domination in Rectangular Grid Graphs and Its Relation to Sub-Quorum Colorings — arXiv:2610.03785

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.03785
License (as archived)
CC0-1.0
Archived
2026-10-06T16:51:14.894Z
SHA-256 of the archived text
c953a129424b70175c186785507d9f8e2f1466c803c12eaebe8b44c759c40dd1
Stable URL of this page
https://metraipolis.com/documento/dc_eea91d07105f

How to cite

Upper Domination in Rectangular Grid Graphs and Its Relation to Sub-Quorum Colorings — arXiv:2610.03785 — arXiv (en), https://arxiv.org/abs/2610.03785 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_eea91d07105f (Metraipolis archive dc_eea91d07105f, sha256 c953a129424b70175c186785507d9f8e2f1466c803c12eaebe8b44c759c40dd1)
BibTeX
@misc{dceea91d07105f,
  title = {Upper Domination in Rectangular Grid Graphs and Its Relation to Sub-Quorum Colorings — arXiv:2610.03785},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.03785},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_eea91d07105f; sha256 c953a129424b70175c186785507d9f8e2f1466c803c12eaebe8b44c759c40dd1},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.03785. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For a graph $G$, the upper domination number $\Gamma(G)$ is the maximum cardinality of a minimal dominating set. A 2023 computational study listed the upper domination number of square grid graphs among the cases for which no general formula was known. We observe that the classical equality $\Gamma(G)=\alpha(G)$ for bipartite graphs immediately determines the parameter for every rectangular grid graph $G_{m,n}=P_m\square P_n$. Namely, \[ \Gamma(G_{m,n})=\left\lceil\frac{mn}{2}\right\rceil. \] We give two short proofs, one through the classical bipartite upper-domination theorem and one through the matching bound $\Gamma(G)+\alpha'(G)\le |V(G)|$. We then compare upper domination with the $2$-independence number and the sub-quorum coloring number of grid graphs. This yields the unconditional chain \[ \Gamma(G_{m,n})\le \beta_2(G_{m,n})\le \psi_{\mathrm{sq}}(G_{m,n}), \] and an explicit formula for the gap between $\Gamma(G_{m,n})$ and $\beta_2(G_{m,n})$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.03785 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T15:19:19.954Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).