On graphs with equal domination and total domination numbers
Abstract
For a graph G without isolated vertices, γ(G)≤γt(G)≤ 2γ(G). While graphs attaining γ(G)=γt(G) have been studied extensively, a complete structural description in the smallest nontrivial case γ(G)=2 has remained open. We resolve this case according to girth. When g(G)≠ 3, we show γt(G)=2 forces G bipartite, give an exact degree-sum criterion for this equality, and show γt(G)∈{2,4} under the additional hypothesis δ(G)≥ 2. When g(G)=3, we use Golumbic's vertex-multiplication operation together with known classifications of graphs of rank $2$ through $5$ to completely list the families satisfying γ(G)=γt(G)=2. As an application, we show that every graph in the extremal family of diameter-two, dominating-vertex-free graphs identified by Erdős and Rényi and classified by Henning and Southey satisfies γt(G)∈{3,6}, so γ=γt=2 never occurs there. Together these results give a full structural dictionary translating γt(G)=2 into concrete, checkable graph-theoretic properties.
Related
- Domination and Total Domination in Johnson graphs
- Equal Lagrange Numbers with Non-Isomorphic Band Graphs: A Counterexample to Schiffler's Problem 6.3
- Settling the total domination-annihilation conjecture for graphs with minimum degree two
- Total {k}-domination in caterpillars: Structural properties and exact results
- Lagrange spectrum for Diophantine approximations of complex numbers with real part equal to one half
BibTeX
@misc{bera2026graphs,
title = {{On graphs with equal domination and total domination numbers}},
author = {Sudip Bera},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03512},
eprint = {2609.03512},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03512},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On graphs with equal domination and total domination numbers
AU - Sudip Bera
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.03512
UR - https://arxiv.org/abs/2609.03512
AB - For a graph G without isolated vertices, γ(G)≤γ_t(G)≤ 2γ(G). While graphs attaining γ(G)=γ_t(G) have been studied extensively, a complete structural description in the smallest nontrivial case γ(G)=2 has remained open. We resolve this case according to girth. When g(G)≠ 3, we show γ_t(G)=2 forces G bipartite, give an exact degree-sum criterion for this equality, and show γ_t(G)∈{2,4} under the additional hypothesis δ(G)≥ 2. When g(G)=3, we use Golumbic's vertex-multiplication operation together with known classifications of graphs of rank $2$ through $5$ to completely list the families satisfying γ(G)=γ_t(G)=2. As an application, we show that every graph in the extremal family of diameter-two, dominating-vertex-free graphs identified by Erdős and Rényi and classified by Henning and Southey satisfies γ_t(G)∈{3,6}, so γ=γ_t=2 never occurs there. Together these results give a full structural dictionary translating γ_t(G)=2 into concrete, checkable graph-theoretic properties.
ER -