Relating the total domination number and the annihilation number of cactus graphs and block graphs

Authors

  • Csilla Bujtás University of Pannonia, Hungary
  • Marko Jakovac University of Maribor, Slovenia and Institute of Mathematics, Physics and Mechanics, Slovenia

DOI:

https://doi.org/10.26493/1855-3974.1378.11d

Keywords:

Total domination number, annihilation number, cactus graph, block graph

Abstract

The total domination number γt(G) of a graph G is the order of a smallest set D ⊆ V(G) such that each vertex of G is adjacent to some vertex in D. The annihilation number a(G) of G is the largest integer k such that there exist k different vertices in G with degree sum of at most |E(G)|. It is conjectured that γt(G) ≤ a(G) + 1 holds for every nontrivial connected graph G. The conjecture was proved for graphs with minimum degree at least 3, and remains unresolved for graphs with minimum degree 1 or 2. In this paper we establish the conjecture for cactus graphs and block graphs.

Published

2018-11-22

Issue

Section

Articles