PreprintCC BY 4.0arXiv
Domination and Total Domination in Johnson graphs
Abstract
In this paper we study domination and total domination of Johnson graphs J(n,k). We establish monotonicity results proving that both $γ(J(n,k))$ and γt(J(n,k)) are non-decreasing with respect to n. We compute exact values for γt(J(n,k)) in specific cases, showing that γt(J(n,2))=⌈2/3(n−1)⌉ for n≥ 4, and determining γt(J(n,3)) for n≥ 6, which depends quadratically on n.
Related
BibTeX
@misc{cornet2026domination,
title = {{Domination and Total Domination in Johnson graphs}},
author = {María Gracia Cornet and Tanja Dravec and Pablo Torres},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04675},
eprint = {2610.04675},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04675},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Domination and Total Domination in Johnson graphs
AU - María Gracia Cornet
AU - Tanja Dravec
AU - Pablo Torres
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04675
UR - https://arxiv.org/abs/2610.04675
AB - In this paper we study domination and total domination of Johnson graphs J(n,k). We establish monotonicity results proving that both $γ(J(n,k))$ and γ_t(J(n,k)) are non-decreasing with respect to n. We compute exact values for γ_t(J(n,k)) in specific cases, showing that γ_t(J(n,2))=⌈2/3(n−1)⌉ for n≥ 4, and determining γ_t(J(n,3)) for n≥ 6, which depends quadratically on n.
ER -