PreprintarXiv licencearXiv
The domination number of the $2$-token graph of path graphs
Abstract
We prove that the domination number of the $2$-token graph of the path Pn is γ(F2(Pn))=d(n) for every n≥ 13, where d(n)=1/10(n2+5n+c) and c is an explicit constant that depends on n bmod 5. This settles a conjecture by Leaños and the authors, who previously proved the upper bound. The lower bound is computer-assisted and follows the method used by Gonçalves, Pinlou, Rao and Thomassé for grid graphs.
Related
- The domination number of the 2-token graph of the complete bipartite graph
- The domination number of the k-token graph of the complete bipartite graph Km,n
- An improved lower bound for the packing number of the 2-token graph of the cycle
- Almost Every Graph Is Reconstructible from Its Token Graphs
- Graphs with Large Vertex–Edge Roman {2}-Domination Number
BibTeX
@misc{troncoso2026domination,
title = {{The domination number of the $2$-token graph of path graphs}},
author = {Emmanuel Acosta Troncoso and Luis Manuel Rivera},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11265},
eprint = {2610.11265},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11265},
}
RIS
TY - UNPB
TI - The domination number of the $2$-token graph of path graphs
AU - Emmanuel Acosta Troncoso
AU - Luis Manuel Rivera
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.11265
UR - https://arxiv.org/abs/2610.11265
AB - We prove that the domination number of the $2$-token graph of the path P_n is γ(F_2(P_n))=d(n) for every n≥ 13, where d(n)=1/10(n^2+5n+c) and c is an explicit constant that depends on n bmod 5. This settles a conjecture by Leaños and the authors, who previously proved the upper bound. The lower bound is computer-assisted and follows the method used by Gonçalves, Pinlou, Rao and Thomassé for grid graphs.
ER -