Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 48 min ago
PreprintCC BY 4.0arXiv

Settling the total domination-annihilation conjecture for graphs with minimum degree two

  • Marko Jakovac
Open at sourcePDFDOICite

Abstract

The total domination number γt(G) of a graph G is the minimum cardinality of a set D⊆ V(G) such that every vertex of G has a neighbor in D. The annihilation number a(G) is the largest integer k for which the sum of the k smallest degrees of G is at most |E(G)|. A well-known conjecture, originating from Graffiti.pc and later formulated explicitly by Desormeaux, Haynes, and Henning, asserts that γt(G)≤ a(G)+1 for every connected nontrivial graph G. The conjecture is known for graphs of minimum degree at least three and for several classes of graphs having vertices of degree one or two. In this paper we settle the minimum-degree-two case. More precisely, we prove γt(G)≤ a(G)+1 for every connected graph G with δ(G)=2. The proof combines two sharp bounds on the total domination number with an estimate for the annihilation number. Moreover, in some specific cases, the stronger inequality γt(G)≤ a(G) holds.

Related

  1. Minimum energy paths for defect annihilation in finite dodecagonal quasicrystal clusters
    Tiejun Zhou, Rong Liu, Gang Cui +3
    arXivPreprintarXiv licenceFull textMathematical physicsCondensed matterarXiv
  2. A Counterexample to an Eternal Domination Conjecture
    Tom Adamczewski, William F. Klostermeyer
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Domination and Total Domination in Johnson graphs
    María Gracia Cornet, Tanja Dravec, Pablo Torres
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. The domination number of the $2$-token graph of path graphs
    Emmanuel Acosta Troncoso, Luis Manuel Rivera
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. On graphs with equal domination and total domination numbers
    Sudip Bera
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{jakovac2026settling,
  title = {{Settling the total domination-annihilation conjecture for graphs with minimum degree two}},
  author = {Marko Jakovac},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.10795},
  eprint = {2609.10795},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.10795},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Settling the total domination-annihilation conjecture for graphs with minimum degree two
AU  - Marko Jakovac
PY  - 2026
DA  - 2026/09/11
PB  - arXiv
DO  - 10.48550/arxiv.2609.10795
UR  - https://arxiv.org/abs/2609.10795
AB  - The total domination number γ_t(G) of a graph G is the minimum cardinality of a set D⊆ V(G) such that every vertex of G has a neighbor in D. The annihilation number a(G) is the largest integer k for which the sum of the k smallest degrees of G is at most |E(G)|. A well-known conjecture, originating from Graffiti.pc and later formulated explicitly by Desormeaux, Haynes, and Henning, asserts that γ_t(G)≤ a(G)+1 for every connected nontrivial graph G. The conjecture is known for graphs of minimum degree at least three and for several classes of graphs having vertices of degree one or two. In this paper we settle the minimum-degree-two case. More precisely, we prove γ_t(G)≤ a(G)+1 for every connected graph G with δ(G)=2. The proof combines two sharp bounds on the total domination number with an estimate for the annihilation number. Moreover, in some specific cases, the stronger inequality γ_t(G)≤ a(G) holds.
ER  -