ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 16 (2019) 183-202
https://doi.org/10.26493/1855-3974.1378.11d
(Also available at http://amc-journal.eu)
Relating the total domination number and the annihilation number of cactus graphs and
block graphs*
Csilla Bujtas
Faculty of Information Technology, University ofPannonia, Egyetem u. 10, 8200 Veszprém, Hungary
Marko Jakovac f
Faculty of Natural Sciences and Mathematics, University ofMaribor, Koroska cesta 160, 2000 Maribor, Slovenia and Institute of Mathematics, Physics, and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia
Received 10 April 2017, accepted 5 August 2018, published online 22 November 2018
The total domination number 7t(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 7t (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.
Keywords: Total domination number, annihilation number, cactus graph, block graph. Math. Subj. Class.: 05C69
* Research of the first author was supported by the National Research, Development and Innovation Office -NKFIH under the grant SNN 116095. The second author acknowledges the financial support from the Slovenian Research Agency (research core funding No. P1-0297). t Corresponding author.
E-mail addresses: bujtas@dcs.uni-pannon.hu (Csilla Bujtas), marko.jakovac@um.si (Marko Jakovac)
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
184
Ars Math. Contemp. 16 (2019) 245-255
1 Introduction
All graphs considered in this paper are nontrivial, finite, simple and undirected. By a nontrivial graph we mean a graph on at least two vertices. If G = (V, E) is a graph, then V = V(G) is the set of vertices of order n(G) = | V|, and E = E(G) is the set of edges of size m(G) = |E|. The degree of a vertex v e V in graph G will be denoted by dG(v). A vertex v of degree 1 is a leaf, while its only neighbor is called a support vertex. If u has at least two neighbors which are leaves, then u is referred to as a strong support vertex. The minimum and maximum degree among the vertices of G are denoted by ¿(G) and A(G), respectively. For v e V(G), the set of its neighbors is denoted by NG(v) and called the open neighborhood of v. We use a similar notation for a set A C V(G), it is defined as NG(A) = UveA NG(v). If G is clear from the context, we simply write d(v), N(v) and N(A) instead of dG(v), NG(v) and NG(A), respectively.
For a graph G, a set D C V(G) is a total dominating set if every v e V(G) has at least one neighbor in D; i.e., if N(D) = V(G). If G does not contain isolated vertices, such a set D always exists, and the minimum cardinality of a total dominating set, denoted by 7t(G), is the total domination number of G. A survey on total domination can be found in [8], and more recently, the topic was thoroughly covered in the book [9]. If Cn is a cycle of length n, its total domination number can be obtained as follows:
Yt(Cn)
n + 1, if n = 2 (mod 4);
mi
otherwise.
For a set B C V we denote by G - B the graph which is obtained from G by deleting the vertices in B and all edges incident with them. Moreover, if v^2 e E and v^2 e E with vi, v2 e V, we use the notations G - viv2 and G+viv2 for the graphs (V, E\{viv2}) and (V, E U {v1v2}), respectively. Let G1 and G2 be two vertex-disjoint graphs and let v1 e V(G1), v2 e V(G2). The identification of vertices v1 and v2 results in a graph G with V(G) = (V(G1) U V(G2) U{v}) \{v1,v2} such that Ng(v) = Ng, (v^ U Ng2 (v2). Moreover, for any vertex u = v, the open neighborhood of u remains the same.
The subdivided star 5(K1i^) is the graph on 2^ +1 vertices which is constructed from the star K^ by subdividing each edge exactly once (left-hand side of Figure 1). The paw is the graph P obtained from K4 by deleting two neighboring edges (right-hand side of Figure 1). A connected graph is called cactus graph if its cycles are pairwise edge-disjoint. Moreover, G is a block graph if each 2-connected component of G is a clique.
U
V2(j		
W 2(	\ ■■■	w
x
U
W
S(Kl/)	P
Figure 1: The subdivided star S(K^), I > 2, and the paw graph P.
Cs. Bujtas andM. Jakovac: Relating the total domination number and the annihilation ... 
185
For a subset S C V(G) we define
£(S,G) = £ dG(v).
ves
Let vi, v2,..., vn be an ordering of the vertices of G such that d(vi) < d(v2) < • • • < d(vn). The annihilation number a(G) is the largest integer k such that d(vj) < m(G). Equivalently, a = a(G) is the only integer satisfying both
a	a+1
^ d(vi) < m(G) and ^ d(v,) > m(G) + 1.
i=i i=i
It is clear by definition that every independent set1 A satisfies J2veA d(v) < m(G) and consequently, the annihilation number is an upper bound on the independence number [11]. The annihilation number was first introduced by Pepper in [12]. The 'annihilation process', which is referred to in this original definition, is very similar to the 'Havel-Hakimi process' (see [7] and [11] for exact descriptions).
In general, a set S of vertices is called an annihilation set if J2veS d(v) < m(G); and S is an optimal annihilation set, if
|S| = a(G) and max{d(v) | v G S} < min{d(u) | u G V(G) \ S}.
In particular, if G is a connected graph on at least 3 vertices, any optimal annihilation set of G contains all leaves.
Assuming that S is an optimal annihilation set, we introduce the following notations. First, denote by d* (G) (or simply by d*) the minimum vertex degree over the set V(G) \ S. Note that d*(G) = d(va(G)+1), and consequently, the value of d*(G) is independent from the choice of the optimal annihilation set S.
The following conjecture can be found in a slightly different form in Graffiti.pc [4], and was later reformulated in [5].
Conjecture 1.1 ([4, 5]). If G is a connected nontrivial graph, then
Yt(G) < a(G) + 1.	(1.1)
By definition, every graph satisfies a(G) > |_^^J. Hence, the formulas given for 7t(Cn) above show that each cycle Cn satisfies the conjecture. Further, if ¿(G) > 3, it was observed that the total domination number is at most |^J [1, 3, 13, 14]. Hence, if ¿(G) > 3, then Yt(G) < a(G) clearly holds, even if G is disconnected. Therefore, it is interesting to study this conjecture for graphs with small minimum degree, i.e. ¿(G) G {1, 2}. So far, Conjecture 1.1 has been proved for only one further important graph class. The following result was established by Desormeaux, Haynes, and Henning in 2013.
Theorem 1.2 ([5]). If T is a nontrivial tree, then Yt(T) < a(T) + 1, and the bound is sharp.
1A set A C V(G) is called an independent set if it induces an edgeless subgraph in G. The largest cardinality of such a vertex set is the independence number of G and denoted by a(G).
186
Ars Math. Contemp. 16 (2019) 245-255
A similar result was proved by Desormeaux, Henning, Rail, and Yeo [6] for the 2-domination number of trees. Very recently, a different proof was given for the same statement by Lyle and Patterson [10]. Namely, their result can be obtained if we replace the total domination number with the 2-domination number in Theorem 1.2.
In this paper we prove Conjecture 1.1 over two further graph classes, namely for cactus graphs and block graphs. These are two natural generalizations of trees and also, for a cactus graph G we have ¿(G) < 2 and there exist block graphs with small minimum degree. Remark that cactus and block graphs are well-studied classes with several applications, see for instance [2]. Our main results are the following ones.
Theorem 1.3. If G is a nontrivial cactus graph, then Yt(G) < a(G) + 1.
Theorem 1.4. If G is a nontrivial block graph, then Yt(G) < a(G) + 1.
To formulate and to prove our results we will use the following function f defined for every finite graph G as
f (G) = n(G) + 3m(G) + ni(G),
where n1 (G) denotes the number of leaves in G. Remark that f is strictly monotone in the sense that if G' is a proper subgraph of G, then f (G') < f (G). Indeed, n(G') + m(G') < n(G) + m(G) clearly holds, and 2m(G') + n1(G') < 2m(G) + n1(G) is true because the deletion of an edge may result in at most two new leaves. Also note that we have f (G) > 7 for any nontrivial, finite and connected graph G.
The paper is organized as follows. In Section 2, we establish several lemmas which will be referred to in later proofs. In Section 3 and 4 we prove Theorem 1.3 and 1.4, respectively. In the last section we discuss the sharpness of our main theorems and arise some related problems.
2 Preliminary results
Here we present some preliminary results on how we can obtain a smaller graph G' from G (mainly, by deleting some edges and/or vertices from G) such that Yt(G') < a(G') + 1 implies Yt(G) < a(G) + 1. First we consider changes related to vertices of small degree.
Lemma 2.1. Assume that G is a connected graph on at least three vertices and it fulfills at least one of the following properties:
(i)	d*(G) < 2;
(ii)	G has a strong support vertex;
(iii)	G contains an induced path vu^^w such that d(u1) = d(u2) = d(u3) = 2;
(iv)	G contains a path u1 u2u3v such that u1 is a leaf and d(u2) = d(u3) = 2;
(v)	G contains two adjacent support vertices.
Then, there exists a nontrivial connected graph G' with f (G') < f (G) such that jt (G') < a(G') + 1 implies Yt(G) < a(G) + 1. Moreover, if G is a cactus graph, then G' can be chosen to be a cactus graph as well; and if G is a block graph, in cases (ii) -(v), G' can be chosen to be a block graph.
Cs. Bujtas andM. Jakovac: Relating the total domination number and the annihilation ... 187
Proof. Since trees and cycles satisfy Conjecture 1.1, we may suppose throughout that G is neither a tree nor a cycle.
(i) First assume that d*(G) < 2. Since G is neither a tree nor a cycle, there exists a vertex v G V(G) with d(v) > 3 which is incident to a cycle. Let e = vu be an edge from that cycle. Clearly, G' = G - e is connected, f (G') < f (G) and m(G') = m(G) - 1. The deletion of an edge does not decrease the total domination number. This establishes 7t(G) < 7t(G'). Consider now an optimal annihilation set S' of G'. By definition, it satisfies £(S',G') < m(G') = m(G) - 1. If u,v G S' then £(S', G) = £(S',G') < m(G) -1; if S' contains exactly one of u and v,thenj](S',G) = £(S',G') + 1 < m(G). In either case a(G) > |S'| = a(G') follows. In the third case u, v G S' and J2(S', G) = XXS', G') + 2 < m(G) + 1. Let V12 denote the set of vertices which have degree 1 or 2 in G. Our assumption d*(G) < 2 implies X(V1j2, G) > m(G) + 1. Since d(v) > 3, we have X(Vi,2 U {v}, G) > m(G) + 4. Therefore, (Vi,2 U {v}) g S' implies that we have a vertex v* g V1j2 which is not contained in S'. If v is replaced with v* in S', we obtain a set S with X(S, G) < ^(S', G) - 1 < m(G). This proves a(G) > |S| = a(G'). If G' satisfies (1.1), we may conclude that the same is true for G:
In the sequel of the proof we will assume that d* (G) > 3.
(ii)	Assume that a vertex v G V(G) has two neighbors u1 and u2 which are leaves in G. Since v remains a support vertex in G' = G - {u1}, it is contained in every total dominating set of G'. This implies 7t(G') = 7t(G). On the other hand, every optimal annihilation set of G contains u1 and hence a(G') < a(G). Then, f (G') < f (G), and Yt(G') < a(G') + 1 implies 7t(G) < a(G) + 1.
(iii)	If vu1u2u3w is an induced path in G and d(u1) = d(u2) = d(u3) = 2, consider the graph G' = G- {u1,u2,u3} + vw. Observe that n(G') = n(G) - 3, m(G') = m(G) - 3, n1(G') = n1(G) and hence, f (G') = f (G) - 12. Let D' be an optimal total dominating set of G' and define D as follows:
In either case, D is a total dominating set in G. Hence, 7t(G) < 7t(G') + 2. Consider next an optimal annihilation set S" of G'. Since dG(v) = dG> (v) and dG(w) = dG> (w), E(S',G) = Z(S',G') < m(G') = m(G) - 3. Our assumption d*(G) > 3 implies that every vertex x with degree d(x) < 2 is contained in every optimal annihilation set of G. Hence, either S' U {«i, u2, u3} is a subset of an optimal annihilation set of G and a(G) > a(G') + 3, or there is a vertex v* G S' with d(v*) > 3. In the latter case, consider S = (S'\{v*}) U{ui, «2, «3}, and observe that £(S,G) < ^(S',G) - 3 + 3 • 2 < m(G). Therefore, a(G) > |S| = |S'| + 2 = a(G') + 2. If G' satisfies inequality (1.1), we have
and that proves the statement for property (iii).
(iv)Letm1m2m3vbeapathinGsuchthatd(u1) = 1 andd(u2) = d(u3) = 2. SinceGis connected and not a path, G' = G-{m1,m2,m3} is nontrivial, and we have f (G') < f (G).
Yt(G) < Yt(G') < a(G') + 1 < a(G) + 1.
Yt(G) < Yt(G') + 2 < a(G') +3 < a(G) + 1
188
Ars Math. Contemp. 16 (2019) 245-255
If D' is an optimal total dominating set of G', then D = D' U {u2, u3} totally dominates all vertices in G. Thus, Yt(G) < |D| < Yt(G') + 2. Next, we choose an optimal annihilation set S' in G' and consider three cases concerning v and S'.
•	If d(v) = 2, then G contains three consecutive degree-2 vertices and, as we have already proved it in (iii), there exists a graph G' with the required property.
•	If v G S', then E(S',G) = £(S',G'), and£(S',G) < m(G') = m(G) - 3. Hence, S = S'U{ui, «2} satisfies £(S, G) = X(S', g) + 3 < m(G), and a(G) > a(G') + 2. This, together with the assumption Yt(G') < a(G') + 1, establishes inequality (1.1) for G.
•	In the last case we assume that both v G S' and d(v) > 3 hold. Then, J2(S', G) = £(S',G') + 1 < m(G') +1 = m(G) - 2. We define S = (S' \{v}) U{u,u2,u3} and observe that X(S, G) = X(S',G) - d(v) + 5 < m(G). Hence, S is an annihilation set in G and we may conclude a(G) > |S| > a(G') + 2. The statement of the lemma is proved by the following chain of inequalities: 7t(G) < Yt(G') + 2 < a(G') + 3 < a(G) + 1.
(v) Let u and v be two leaves in G with support vertices u' and v' respectively such that uu', vv', u'v' G E(G). Since G is not a path, at least one of these two support vertices, say u', is of degree of at least 3. Then, we define G' = G - uu' + uv and observe that f (G') = f (G) - 1. Let D' be an optimal total dominating set of G'. Since v is a support vertex in G', v g D' must hold. Moreover, since NG/ (u) C NG/ (v'), we can choose D' such that u does not belong to it. Then, D = (D' \ {v}) U {u'} is a total dominating set in G. Hence, Yt(G) < |D| = |D'| = 7t(G'). By construction, every vertex has the same degree in G as in G' with the two exceptions v and u', for which dG (u') = dG> (u') + 1 and dG(v) = dG/ (v) - 1. Hence, any optimal annihilation set S' of G' satisfies one of the following cases.
•	If u',v G S' or u',v G S', then (S', G) = £(S',G') < m(G') = m(G). Therefore, a(G) > |S'| = a(G').
•	If v G S' and u' G S', the^(S',G) = £(S',G') - 1 < m(G') - 1 = m(G) - 1. Therefore, a(G) > |S'| = a(G').
•	If u' G S' and v G S', then £(S', G) = ^(S', G') + 1 < m(G') + 1 = m(G) + 1. We define S = (S' \ {u'}) U {v}. By our assumption, dG(u') > 3 and so, we have XXS, G) = X(S', G) - dG(u') + 1 < m(G) + 1 - dG(u') + 1 < m(G) - 1. This implies a(G) > a(G').
We have seen that for all possible cases a(G') < a(G) and 7t(G) < 7t(G'). Together with the condition that G' satisfies (1.1), these imply 74(G) < Yt (G') < a(G') + 1 < a(G) + 1.
At the end of the proof we remark that all the above transformations result in a cactus graph G', if G was of the same type. Further, with the only exception of (i), the obtained graphs stay block graphs if G is a block graph.	□
Lemma 2.2.
(i) For an integer £ > 3, let Q = Ke be a complete subgraph of the connected graph G such that Q contains exactly one vertex, say x, of degree larger than £ - 1. Assume further that G' = G - (V(Q) \ {x}) satisfies Yt(G') < a(G') + 1. Then, Yt(G) < a(G) + 1 follows.
Cs. Bujtas andM. Jakovac: Relating the total domination number and the annihilation ... 
189
(ii) Let C be a cycle in a connected graph G such that C contains exactly one vertex which is of degree larger than 2. Then, there exists a nontrivial connected graph G' with f (G') < f (G) such that Yt(G') < a(G') + 1 implies 7i(G) < a(G) + 1. Moreover, if G is a cactus graph, then G' can be chosen to be a cactus graph as well.
Proof. (i) We suppose d(x) > £ > 3 and V(Q) = jvi, v2,..., x}. By definition, m(G') = m(G) - Q. For any total dominating set D' of G', D' U{x} is a total dominating set of G. Hence, 7t(G) < 7t(G') + 1. Now, let S' be an optimal annihilation set in G'.
•	If x G S', we define S = (S'\{x}) U {v1,..., vy t j+1}. Since dG>(x) > 1, we E(S, G) < £(S', G') - 1 + (L3J +1) (£ - 1). 3
•	If x G S', let S = S' U {v1,..., vytj}. Then, since £ > 3, we have
E(S, G) < £(S', G') + |jj (£ - 1) < £(S', G') - 1 + ( |jj + (£ - 1).
Observe that in either case and for every £ > 3, the relation |S| > |S'| + 1 holds. Moreover, as J2(S', G') < m(G'), we may estimate J2(S, G) as follows:
£(S,G) < m(G') - 1+( 3 +^(£ - 1)
= m(G) - ( 2 ) - 1 +
+ 1 (£ -1)
= m(G) -
1H2 -
- 1 + 1
< m(G).
Here, the last inequality can be directly checked for £ =3, 4 and 5. If £ > 6, this clearly follows from f - 3 - 1 > 0. We conclude that S is an annihilation set in G and therefore,
a(G) > |S| > |S'| + 1 = a(G') + 1. Together with the condition given in (i) for G',
Yt(G) < Yt(G') + 1 < a(G') +2 < a(G) + 1
follows. This finishes the proof of (i).
(ii) Since C3 = K3, it suffices to prove (ii) for cycles C = Ce of length £ > 4. If d* (G) < 2 or £ > 6, Lemma 2.1(i) and 2.1(iii) establish the statement. Henceforth, we will suppose that d*(G) > 3 and £ = 4 or 5. Let xv1... v^_1x be the cycle C such that
d(x) > 3.
First, assume that £ + dG(x) > 8; i.e., at least one of £ = 5 and dG (x) > 4 holds. Let G' = G - (V(C) \ {x}) and let D' be an optimal total dominating set of G'. Observe that D = D' U {v2, v3} is a total dominating set in G and consequently, Yt(G) < Yt(G') + 2. Now, fix an optimal annihilation set S' in G' and consider the following two subcases.
•	If x G S', we have E(S', G) = £(S', G') < m(G') = m(G) - £. Then, we define S = S' U{v1,v2} and observe that £(S,G) = ¿(S',G) + 2 • 2 < m(G) - £ + 4 < m(G). This proves a(G) > |S| = a(G') + 2.
•	If x G S', we have £(S', G) = £(S', G') + 2 < m(G') + 2 = m(G) - £ + 2. In this case, consider S = (S' \ {x}) U {v1, v2, v3}. For this set,
X)(S, G) < ^(S', G) - dG(x) + 3 • 2 < m(G) - £ - dG(x) + 8 < m(G)
190
Ars Math. Contemp. 16 (2019) 245-255
holds under the present assumption £ + dG(x) > 8. Therefore, we have a(G) > |S| = a(G') +2.
In either subcase, if G' satisfies (1.1), we may conclude that
Yt(G) < Yt(G') +2 < a(G') + 3 < a(G) + 1.
In the other case, C = C4 and dG(x) = 3. Here, we define G' = G - V(C). Since dG (x) = 3, G' is connected. If G' consists of only one vertex, Yt(G) = 2 < a(G) + 1 can be proved directly. Hence, we may assume that G' is nontrivial. Let D' be an optimal total dominating set in G' and observe that, also in this case, D = D' U {v2,v3} is a total dominating set in G. Hence, Yt(G) < Yt(G') + 2. On the other hand, let S' be an optimal annihilation set in G'. Since there is at most one edge between S' and V(C), ¿(S', G) < ¿(S', G') + 1 < m(G') + 1 = m(G) - 4. Moreover, for S = S' U {v^ v2}, we obtain ¿(S, G) = ¿(S', G) + 4 < m(G), from which a(G) > a(G') + 2 follows. Thus, if G' satisfies (1.1), the desired inequality Yt(G) < a(G) + 1 holds again.	□
The analogue of the following proof was given by Desormeaux et al. [5] inside the proof of Theorem 1.2. There, both H and T were restricted to be a tree. Here, we restate and prove the lemma in a more general form, where H can be an arbitrary connected graph.
Lemma 2.3. Let H be a nontrivial connected graph and T be a tree such that V(H) n V (T) = 0. Suppose that w G V (H), u G V (T), and v is a leaf in T such that d(u, v) > 3. If G is obtained from H and T by identifying w and u, there exists a connected graph G' with f (G') < f (G) such that Yt(G') < a(G') + 1 implies Yt(G) < a(G) + 1.
Proof. First note that the statement follows from Lemma 2.1 (i) if d*(G) < 2. Hence, we may suppose that d*(G) > 3. Assume that T is rooted in u and choose a leaf v1 G V (T) which is of maximum distance from u. Let v2 be the parent of v1, and v3 be the parent of v2. By assumption, d(u, v1) > 3 and hence, v4 = u (i = 1,2,3).
We will consider graphs G' obtained from G by removing a set of vertices from V(T) in such a way that G' will stay connected. Throughout, S' will denote an optimal annihilation set in G'.
If v2 is a strong support vertex, Lemma 2.1 (ii) implies the statement. So, we may suppose that v1 is the only leaf of the support vertex v2. Since v1 is of maximum distance from u, d(v2) = 2 also follows. Remark that the same is true for any other leaf and its support vertex, if the leaf is of maximum distance from u. Suppose that d(v3) > 3 and let G' = G - {v1,v2}. So m(G') = m(G) - 2. If v3 is a support vertex in G', then v3 belongs to a minimum total dominating set D' of G'. If v3 is not a support vertex, then every child of v3 is a support vertex of degree 2. If a leaf-neighbor of a child of v3 belongs to D', then we can simply replace it in D' with the vertex v3. In either case, we may assume that v3 g D'. Thus the set D = D' U {v2} is a total dominating set of G, and so Yt(G) < |D| = |D'| + 1 = Yt(G') + 1. Independently of whether vertex v3 lies in S' or not we have ¿(S', G) < ¿(S', G') + 1 < m(G') + 1 = m(G) - 1. Consider S = S' U {vj. Then ¿(S, G) = ¿(S', G) + d(v1) < m(G), implying that a(G) > |S| = |S'| + 1 = a(G') + 1. By assumption, we have that Yt(G') < a(G') + 1. Therefore,
Yt(G) < Yt(G') + 1 < a(G') + 2 < a(G) + 1.
Cs. Bujtas andM. Jakovac: Relating the total domination number and the annihilation ... 
191
So, we may suppose that d(v3) = 2. Now we have three consecutive vertices v1, v2,v3 with degrees d(v1) = 1 and d(v2) = d(v3) = 2. Thus, by Lemma 2.1(iv), there exists a graph G' with f (G') < f (G) which satisfies the statement.	□
The following lemmas will be needed to cover two specific cases in the proofs of Theorems 1.3 and 1.4. Therefore, we give the proof for both cases here.
Lemma 2.4. Let H and F = S(K1,g) be two vertex-disjoint graphs with n(H) > 3 and t > 2. Assume that w is a vertex of H such that H — {w} is connected and u is the central vertex of the subdivided star F .If G is the graph obtained from H and F by identifying w and u, and Yt(G — V(F)) < a(G — V(F)) + 1, then Yt(G) < a(G) + 1.
Proof. Suppose the subgraph F of G is rooted in u. We denote with vi,... ,vg the children of u, and with w1,... ,wg the leaves. By our assumption, G' = G — V (F) = G —
{u,v1,... ,vg,w1,..., wg} is a nontrivial connected graph, and m(G') = m(G)—dG(u) — t. If D' is a minimum total dominating set of G', then D = D' U {u,v1,..., vg} is a total dominating set of G,and hence Yt(G) < |D| = ID'l+t+1 = jt(G')+t+1. Now, consider an optimal annihilation set S' in G'. Independently of whether the vertices in NG> (u) are inside S' or not, we have £(S', G) <J2(S', G') + dG(u) — t < m(G') + dG(u) — t = m(G) — 2t. Let S = S'U{v1,w1,... ,we}. Then Y,(.S,G) = Y,(S',G) + 2+1 < m(G) — 2t+1+2 < m(G), since t > 2. Then, we have a(G) > |S| = |S'| +1 +1 = a(G')+1 +1. By assumption, we have that jt(G') < a(G') + 1. Therefore,
Yt(G) < Yt(G') + t +1 < a(G') + t + '2 < a(G) + 1.	□
Lemma 2.5. Let H and P be two vertex-disjoint graphs, where P is the paw graph and H is a nontrivial connected graph. Moreover, let z be a vertex of H and let x be a vertex of P with dP (x) = 2. Assume that G is the graph obtained from H and P by identifying z and x. Then, there exists a connected graph G' with f (G') < f (G) such that jt(G') < a(G') + 1 implies Yt(G) < a(G) + 1.
Proof. If H = K2, then G is a graph of order 5 satisfying Yt(G) = 2 and a(G) = 3. Thus, (1.1) holds for G. From now on, we assume that n(H) > 3. We denote the neighbors of x in P with u and w, and let v be the leaf neighbor of u. Two subcases will be considered depending on the degree d(x) of x in G.
First suppose that d(x) = 3. Denote the third neighbor of x outside P with y. Since H had at least three vertices, y is not a leaf, and hence G' = G — V(P) = G — {x, u, v, w} is not a trivial graph. Also, m(G') = m(G) — 5. If D' is a minimum total dominating set of G', then D = D' U {u, w} is a total dominating set of G, and hence Yt(G) < |D| = |D'| + 2 = Yt(G') + 2. If S' is an optimal annihilation set of G', we have (S', G) < J2(S', G') + 1 < m(G') + 1 = m(G) — 4. Let S = S' U {u,v}. Then Y,(.S,G) = J2(S', G) + d(u) + d(v) < m(G) — 4 + 3+1 = m(G), and we have a(G) > |S| = |S'| + 2 = a(G') + 2. Then, jt(G') < a(G') + 1 implies
Yt(G) < Yt(G') +2 < a(G') + 3 < a(G) + 1.	(2.1)
Now, suppose d(x) > 4. In this case let G' = G—{u, v, w}, and so m(G') = m(G)—4. If D' is a minimum total dominating set of G', then D = D' U {u, w} is a total dominating set of graph G, and hence Yt(G) < |D| = |D'| + 2 = Yt(G') + 2. Now, let S' be an optimal annihilation set in G'. If x <£ S', then J2(S', G) = J2(S', G'). In this case, let
192
Ars Math. Contemp. 16 (2019) 245-255
S = S'U{u,v}. Then ^(S,G) = £(S',G) + d(u) + d(v) < m(G) -4 + 3 + 1 = m(G), and we have a(G) > |S| = |S'| + 2 = a(G') + 2. If 7i(G') < a(G') + 1, the chain (2.1) of inequalities verifies the statement.
But, if x e S', then £(S',G) = £(S',G') +2 < m(G') + 2 = m(G) - 4 +
2	= m(G) — 2. In this case, let S = (S'\{x}) U {u, v, w}. Since d(x) > 4 we have £(S, G) = £(S', G) — d(x) + 3+1 + 2 < m(G) — 2 — 4 + 6 = m(G) implying that a(G) > |S| = |S'| + 2 = a(G') + 2. By assumption we have that 7i(G') < a(G') + 1. Therefore, we get again (2.1) which proves the lemma.	□
3	Cactus graphs
Recall that a cactus graph is a connected graph such that any two of its cycles are pairwise edge-disjoint. If the cactus graph does not contain any cycles, then it is a tree. Let C1 and C2 be two cycles in the cactus graph. We define
d (C\C2) = min{d(u,v) | u e V (C1) ,v e V (C2)},
where d(u, v) denotes the distance between vertices u and v. Let x1 e V (C^ and x2 e V (C^ be two vertices such that d(x1, x2) = d (C\ C2). Then we call x1 and x2 exit-vertices of cycles C1 and C2, respectively. A cycle is said to be an outer cycle if it has at most one exit-vertex. If a cactus graph is not a tree, then by the definition of a cactus graph it must contain at least one outer cycle. Note that a cactus graph, which is neither a tree nor a cycle, does not contain exit-vertices if and only if it is unicyclic. In this case, we will take an arbitrary vertex of the unique cycle whose degree is at least 3 for the role of the exit-vertex x. In the right-hand side graph of Figure 2, we have three possibilities for the choice of that vertex x (either x1 or x2 or x3). In both cases, whether a cactus graph has one or more cycles, vertex x will always have degree d(x) > 3.
Figure 2: Two examples of cactus graphs. The first one has three outer cycles (C1, C2, C4), its exit-vertices are filled with black. The second cactus graph is unicyclic with one outer cycle, and has no exit-vertices.
In this section we prove Conjecture 1.1 for cactus graphs. Recall the corresponding statement.
Cs. Bujtas andM. Jakovac: Relating the total domination number and the annihilation ... 
193
Theorem 1.3. If G is a nontrivial cactus graph, then Yt(G) < a(G) + 1.
Proof. We proceed by induction on the value of function f (G) > 7. For f (G) = 7 we have G = K2, and Yt(K2) = 2 = a(K2) + 1. For the inductive hypothesis, let f (G) > 8 and assume that for every nontrivial cactus graph G' with f (G') < f (G) we have Yi(G') < a(G') + 1. If G is a tree, then by Theorem 1.2 the result follows. Also, if G is a cycle, the statement is true. Thus, we may suppose that G contains at least one cycle as a proper subgraph. We denote with Ck, k > 3, an outer cycle of G.
Through most part of the proof, we will consider cactus graphs G' formed from G by removing a set of vertices in such a way that graph G' will still be a connected cactus graph and consequently f (G') < f (G) will hold. Throughout, S' will denote an optimal annihilation set in G'. We consider two cases.
Case 1: All vertices from V(Ck)\{x} have degree 2.
Lemma 22(ii) and our inductive hypothesis together imply that Yt(G) < a(G) + 1.
Case 2: There exists a vertex from V(Ck )\{x} that has degree at least 3.
Since V(Ck)\{x} contains some vertices of degree at least 3, and Ck is an outer cycle, there are trees attached to those vertices. Suppose, we root all trees in the vertices V(Ck)\{x} to which these trees are attached. Amongst those trees we consider the tree T with the largest height h(T) = max{d(u, v) | u = V(Ck) n V(T), v e V(T)}. Denote this maximum height with h > 1 and let u be the vertex of V(Ck)\{x} to which tree T is attached. We consider three subcases.
Case 2.1: h > 3.
Since h > 3, there exists a leaf v e V(T) such that d(u, v) = h > 3. By Lemma 2.3 and our inductive hypothesis, graph G satisfies (1.1).
Case 2.2: h = 2.
We only need to consider the four cases shown in Figure 3. All other cases for h = 2 can be proved with the help of Lemma 2.1(ii) and 2.1(v).
(a)	(b)	(c)	(d)
Figure 3: Cases for h = 2.
We first start with the case in Figure 3(a). In this case, we have a subdivided star Ki^, I > 2, attached to the outer cycle, and hence, by Lemma 2.4 and our inductive hypothesis for G' = G - V(S(Km)), graph G satisfies (1.1).
Next, we consider the case in Figure 3(b). Vertex u has only one path of length 2 attached to it, i.e. d(u) = 3. We suppose that u has a neighbor u1 in V(Ck)\{x} with
194
Ars Math. Contemp. 16 (2019) 245-255
degree d(ui) = 2. We denote with v the only child of u, and with w the only child of
v. Let G' = G — {u, u1, v, w}, and so m(G') = m(G) — 5. If D' is a minimum total dominating set of G', then D = D' U{u,v} is a total dominating set of graph G, and hence
7t(G) < |D| = |D'| +2 = 7i(G' ) + 2. Independently of whether the neighbors of u and u1 in G' are inside S' or not, wehavej](S',G) < £(S',G') + 2 < m(G') + 2 = m(G) — 3. Let S = S' U {v, w}. Then £(S, G) = £(S', G) + d(v) + d(w) < m(G) — 3 + 2 + 1 = m(G), and we have a(G) > |S| = |S' |+2 = a(G')+2. Applying our inductive hypothesis to G', we have that Yt (G') < a(G') + 1. Therefore,
Yt(G) < Yt(G') +2 < a(G') + 3 < a(G) + 1.
We proceed with the case in Figure 3(c). Vertex u has again only one path of length 2 attached to it, i.e. d(u) = 3. We suppose that u has a neighbor u1 in V(Ck)\{x} with degree d(u1) = 3, and a path of length 1 attached to it. Denote its child with v1. We also denote with v the only child of u, and with w the only child of v. Let G' =
G — {u, v, w, u1, v1}, and so m(G') = m(G) — 6. If D' is a minimum total dominating set of G', then D = D' U {u, v, u1} is a total dominating set of G, and hence Yt(G) < |D| = |D'| + 3 = Yt(G') + 3. Independently of whether the neighbors of u and u1 in G' are inside S' or not, we have £(S', G) < E(S', G') + 2 < m(G') + 2 = m(G) — 4. Let S = S' U {v, w, v1}. Then £(S, G) = £(S', G) + d(v) + d(w) + d(v1) < m(G) —
4	+ 2 + 1 + 1 = m(G), and we have a(g) > |S| = |S'| + 3 = a(G') + 3. Applying our inductive hypothesis to G', we have that Yt(G') < a(G') + 1. Therefore,
Yt(G) < Yt(G') +3 < a(G') + 4 < a(G) + 1.
The last case to consider is the one shown in Figure 3(d). Denote with u1,..., uk-1 all vertices of V(C)\{x}. Each of those vertices must have one path of length 2 attached to it, i.e. d(uj) = 3 for every i € {1,..., k — 1}, since otherwise this case would be covered by one of the previous three cases. Clearly, vertices u1 and uk-1 are neighbors of x. Denote for every i € {1,..., k — 1} with v4 the only child of u4, and with w4 the only child of v4. We consider two subcases.
First, suppose that d(x) = 3. Denote the third neighbor of x outside Ck with y. If vertex y was a leaf, then we could exchange vertex x with one of u/s, and use the proof for the case in Figure 3(c). Hence, we may assume that y is not a leaf and graph G' = G — {x,u1,... ,uk-1,v1,... ,vk-1, w1,... ,wk-1} is not a trivial cactus graph. Also, m(G') = m(G) — 3k +1. If D' is a minimum total dominating set of G', then D = D' U {u1,..., uk-1, v1,..., vk-1} is a total dominating set of G, and hence Yt(G) < |D| = |D'| + 2k — 2 = Yt(G') + 2k — 2. Independently of whether y is inside S' or not we have (S',G) < ^(s', G') + 1 < m(G') + 1 = m(G) — 3k + 2. Let
5	= S'U{v1,..., vfc_1, w1,..., wfc_1}. Then £(S, G) = E(S', G)+2(k—1) + (k—1) < m(G) — 3k + 2 + (3k — 3) = m(G) — 1, and we have a(G) > |S| = |S'| + 2k — 2 = a(G') + 2k — 2. Applying our inductive hypothesis to G', we have that Yt(G') < a(G') + 1. Therefore,
Yt(G) < Yt(G') + 2k — 2 < a(G') + 2k — 1 < a(G) + 1.
Now, suppose that d(x) > 4. Let G' = G — {u1,..., uk-1, v1,..., vk-1, w1,..., wk-1}, and so m(G') = m(G) — 3k + 2. If D' is a minimum total dominating set of G', then D = D' U {u1,..., uk-1, v1,..., vk-1} is a total dominating set of G, and hence
Yt(G) < |D| = |D'| + 2k — 2 = Yt(G') + 2k — 2. If x € S', the^(S',G) = ^(S',G').
Cs. Bujtas andM. Jakovac: Relating the total domination number and the annihilation ... 
195
In this case, let S = S' U {vi,..., vfc_i, wi,..., wfc_i}. Then £(S,G) = £(S',G) + 2(k - 1) + (k -1) < m(G) -1, and we have a(G) > |S| = |S'| + 2k - 2 = a(G') + 2k - 2. Applying our inductive hypothesis to G', we have that Yt(G') < a(G') + 1. Therefore,
7i(G) < 7i(G') + 2k - 2 < a(G') + 2k - 1 < a(G) + 1.
If x € S', then £(S', G) = £(S', G') + 2 < m(G') + 2 = m(G) - 3k + 2 + 2 = m(G) - 3k + 4. In this case, let S = (S'\{x}) U {u1, v1,..., vk_1, w1,..., wk_1}. Since d(x) > 4 we have £(S,G) = £(S', G)-d(x)+d(u1)+2(k-1) + (k-1) < m(G)-3k+ 4 -4 + 3 + 3(k - 1) = m(G), implying that a(G) > |S| = |S'| + 2k - 2 = a(G') + 2k - 2. By our inductive hypothesis, we have that jt (G') < a(G') + 1. Therefore,
7i(G) < Yt(G') + 2k - 2 < a(G') + 2k - 1 < a(G) + 1. Case 2.3: h = 1.
It suffices to consider only those cases shown in Figure 4. Note that all other cactus graphs with h =1 would involve two leaves at distance of at most 3, and hence these cases can be reduced to the direct application of Lemma 2.1(ii) and 2.1(v).
(a)	(b)	(c)
Figure 4: Cases for h = 1.
First, consider Figure 4(a). Here, we assume that vertex u has degree d(u) = 3, and its neighbors in V(Ck)\{x}, namely u1 and u2, are of degree 2. Denote the child of u with v. In this case we want u1 and u2 to be different from the exit-vertex x. Let G' =
G - {u, v, u1, u2}, and so m(G') = m(G) - 5. If D' is a minimum total dominating set of G', then D = D' U{u,u4} with i = 1 or i = 2 is a total dominating set of G, and hence
Yt(G) < |D| = |D'|+2 = Yt(G')+2. Independently of whether the neighbors of u1 and u2 in G' are inside S' or not, we have E(S',G) < E(S',G')+2 < m(G')+2 = m(G) - 3. Let S = S' U{u1,v}. Then £(S,G) = ^(s', G) + d(u1) + d(v) < m(G) - 3 + 2 + 1 = m(G), and we have a(G) > |S| = |S'|+2 = a(G' )+2. Applying our inductive hypothesis to G', we have that Yt(G') < a(G') + 1. Therefore,
Yt(G) < Yt(G') +2 < a(G') + 3 < a(G) + 1.
We proceed with the case in Figure 4(b). Denote with u the vertex of V(Ck)\{x} with one path of length 1 attached to it, i.e. d(u) = 3, and let v be its only child. One of the neighbors of u must clearly be vertex x because otherwise we would have the case in Figure 4(a). Suppose that all other vertices in V(Ck )\{x}, denote them with w1,..., wk_2, have degree 2.
196
Ars Math. Contemp. 16 (2019) 245-255
First suppose that k = 3. In this case x, u, v and wi induce the paw graph. Then, by Lemma 2.5 and our inductive hypothesis, graph G satisfies (1.1).
Suppose that k > 4. Let G' = G — {u, v, w1,w2}, and so m(G') = m(G) — 5. Remark that G' remains a cactus graph. If D' is a minimum total dominating set of G', then D = D' U{u,w1} is a total dominating set of G,and hence Yt(G) < |D| = |D'| +2 = 7t(G') + 2. Independently of whether x and w3 is inside S' or not we have J2 (S', G) < ¿(S', G') + 2 < m(G') + 2 = m(G) — 3. Let S = S' U {v, wj. Then (S, g) = XXS', G) + d(v) + d(w1) < m(G) — 3+1 + 2 = m(G), and we have a(G) > |S| = |S'| + 2 = a(G') + 2. Applying our inductive hypothesis to G', we have that Yt(G') < a(G') +1. Therefore,
Yt(G) < Yt(G') +2 < a(G') + 3 < a(G) + 1.
We finish with the case in Figure 4(c). Denote with u1 and u2 two vertices in V(Ck)\{x} each with one path of length 1 attached to it, i.e. d(u1) = d(u2) = 3, and let v1 and v2 be the only child of u1 and u2, respectively. The exit-vertex x must be the neighbor of both u1 and u2 because otherwise we would have the case in Figure 4(a). We denote all vertices in V(Ck)\{x} between vertex u1 and u2 with w1,..., wk-3. Those vertices have all degree 2.
If k = 3, the statement follows immediately from the hypothesis and Lemma 2.1 (v), since in this case the support vertices of v1 and v2 are adjacent. Thus, we first suppose that k = 4. Let G' = G — {u1, v1, u2, v2, w1}, and so m(G') = m(G) — 6. If D' is aminimum total dominating set of G', then D = D' U {x, u1, u2} is a total dominating set of G, and hence Yt(G) < |D| = |D' | + 3 = Yt(G') + 3. Independently of whether x G S' or x G S', we have X(S',G) < jr(S',G')+2 < m(G') + 2 = m(G)—4. LetS = S'U{v1,v2,w1}. Then £(S, G) = £(S', G) + d(v1) + d(v2) + d(w1) < m(G) — 4 + 1 + 1 + 2 = m(G), and we have a(G) > |S| = |S'| + 3 = a(G') + 3. Applying our inductive hypothesis to G', we have that Yt(G') < a(G') + 1. Therefore,
Yt(G) < Yt(G') +3 < a(G') + 4 < a(G) + 1.
Now, suppose that k = 5. We make a similar cut than the one for k = 4. Let
G' = G — {u1, v1, u2, v2, w1, w2}, and so m(G') = m(G) — 7. If D' is aminimum total dominating set of G', then D = D' U {x, u1, u2} is a total dominating set of G, and hence Yt(G) < |D| = |D'| + 3 = Yt(G') + 3. For any optimal annihilation set
S' of G', we have X(S',g) < ^(S', G') + 2 < m(G') + 2 = m(G) — 5. Let S = S'U{v1,v2,w1}. Then ¿(S,G) = £(S',G) + d(v1) + d(v2) + d(w1) < m(G) — 1, and a(G) > |S| = |S'| + 3 = a(G') + 3 follows. Applying our inductive hypothesis to G', we have that Yt(G') < a(G') + 1. Therefore,
Yt(G) < Yt(G') +3 < a(G') + 4 < a(G) + 1.
For the last case, let k > 6. We have three consecutive vertices w1, w2, w3 with degree d(w1) = d(w2) = d(w3) = 2. Furthermore, vertices u1 and w4 (or u1 and u2, if k = 6) are not adjacent. Thus, by Lemma 2.1 (iii) and our inductive hypothesis, graph G satisfies (1.1).
These cover all possible cases which can occur in a cactus graph which is neither a tree nor a cycle. Hence, Conjecture 1.1 is true for the family of cactus graphs.	□
Cs. Bujtas andM. Jakovac: Relating the total domination number and the annihilation ... 
197
4 Block graphs
Recall that a block graph is a connected graph in which every 2-connected component (block) is a clique. Block graphs have minimum degree at least 3 if its building blocks are complete graphs Kk, k > 4. Thus, Conjecture 1.1 obviously holds for them. On the other hand, block graphs also contain blocks K2 and K3, and therefore, it clearly makes sense to study Conjecture 1.1 on block graphs.
We proceed with a similar definition than the one for cactus graphs. If all cliques in a block graph are K2, then it is a tree. For every k > 3 we will call complete graph Kk a complex clique. Let K1 and K2 be two complex cliques in the block graph. We define
d (K 1,K2) = min{d(u, v) | u G V (K1) ,v G V (K2)},
where d(u, v) denotes the distance between vertices u and v. Let x1 G V (K^ and x2 G V (K2) be two vertices such that d(x1, x2) = d(K1, K2). Then we call x1 and x2 exit-vertices of complex cliques K1 and K2, respectively. Notice that a complex clique might not have any exit-vertices if it is the only complex clique in the block graph. A complex clique will be called an outer complex clique if it has at most one exit-vertex. If a block graph is not a tree, then by the definition of a block graph it must contain at least one outer complex clique.
Now, we are ready to present a proof of Theorem 1.4. Recall its statement.
Theorem 1.4. If G is a nontrivial block graph, then Yt(G) < a(G) + 1.
Proof. We proceed by induction on the value of function f (G). For f (G) = 7 we have G = K2, and Yt(K2) = 2 = a(K2) + 1. For the inductive hypothesis, let f (G) > 8 and assume that for every nontrivial block graph G' with f (G') < f (G) we have Yi(G') < a(G') + 1. If G does not contain complex cliques, then it is a tree, and by Theorem 1.2 the result follows. Also, if G is a complete graph, i.e. G = Ke, I > 2, we have 7t(Ke) = 2 < a(Ke) + 1. Thus, we may suppose that G is neither a tree nor a complete graph, but contains at least one complex clique as a proper subgraph. We denote with Kk an outer complex clique of G. Similarly as in the proof for cactus graphs, all outer complex cliques in the figures will be drawn with an exit-vertex x even though a unique complex clique in a block graph does not have one. In the latter case, we denote with x an arbitrary vertex of clique Kk whose degree is at least k. In both cases, whether a block graph has one or more complex cliques, vertex x will have degree d(x) > k.
Through most part of the proof, we will consider block graphs G' formed from G by removing a set of vertices in such a way that graph G' will still be a connected block graph and consequently f (G') < f (G) will hold. Throughout, S' will denote an optimal annihilation set in G'. We consider two cases.
Case 1: All vertices from V(Kk )\{x} have degree k - 1.
Let u1,..., uk-1 be vertices from V(Kk)\{x} with degree k - 1. By Lemma 2.2(7), and inductive hypothesis for G' = G - {u1,..., uk-1}, graph G satisfies (1.1).
Case 2: There exists a vertex from V(Kk)\{x} that has degree at least k.
Since V(Kk)\{x} contains vertices of degree at least k, and Kk is an outer complex clique, there are trees attached to those vertices. Suppose, we root all trees in the vertices V(Kk)\{x} to which these trees are attached. Amongst those trees we consider the tree
198
Ars Math. Contemp. 16 (2019) 245-255
T with the largest height h. Let u be the vertex of V(Kk)\{x} to which this tree T is attached. We split the problem into three subcases.
Case 2.1: h > 3.
Since h > 3, there exists a leaf v G V(T) such that d(u, v) = d > 3. By Lemma 2.3 and our inductive hypothesis, graph G satisfies (1.1).
Case 2.2: h = 2.
We only need to consider cases shown in Figure 5. All other cases for h = 2 can be proved directly with the help of Lemma 2.1(ii) and 2.1(v).
(a)	(b)
Figure 5: Cases for h = 2.
We start with the case in Figure 5(a) and suppose that there exists a subdivided star S(Ki^), I > 2, attached to the outer complex clique. By Lemma 2.4 and our inductive hypothesis for G' = G - V(S(Kii^)), graph G satisfies (1.1).
In the case shown in Figure 5(b), there are vertices in V(Kk)\{x} such that a path of length 2 is attached to them. We denote such vertices with ui,..., ua. Since h = 2, we must have at least one such vertex. Thus, a G {1,..., k - 1}. For each i G {1,..., a} we denote with ui the child of u, and with ui' the child of ui. Also, we may suppose that at most one vertex in V(Kk)\{x} has a path of length 1 attached to it. If we had more such vertices, then we would have two adjacent support vertices and we could prove the statement by referring to Lemma 2.1 (v). Hence, denote this vertex with v and let b denote the Boolean value whether it exists in V(Kk)\{x} or not, i.e. b G {0,1}. We denote the child of v with v'. There may also be some vertices in V(Kk)\{x} without a path attached to them. Denote them with w,..., wc, c G {0,..., k - 2}. Clearly, we have a + b + c = k — 1. Let G' = G — {ui,... ua, ui,... ua, u'',..., ua', v,v',wi,..., wc}, and so m(G') = m (G) - (ZU—1 + 2a + b). If D' is a minimum total dominating set of G', then D = D' U {u,..., ua, u', ..., ua, v} is a total dominating set of G, and hence Yt(G) < |D| = |D'| + 2a + b = Yt(G') + 2a + b. Independently of whether x is inside S' or not we have
E(S',G) < E(S',G') + (k - 1)
= m(G') + (k - 1) = m(G) - f k(k - 1) + 2a + ^ + k - 1.
Cs. Bujtas andM. Jakovac: Relating the total domination number and the annihilation ... 
199
Let S = S' U {ui,..., ua, u'/,... ua', v'} and observe that
^(S, G) = ^(S', G) + d(u') + • • • + d(<) + d(u'/) + • • • + d(ua') + d(v') < m(G) - ^ k(k- 1) + 2a + b^ + k - 1 + 3a + b. First, suppose that 1 < a < k - 2 holds. Then,
m(G) - ( k(k - 1) +2a + b ) + k - 1 + 3a + b = m(G) - -k2 + 3k + a - 1
2 7 2 2
1 5	1
< m(G) - -k2 + -k - 3 = m(G) - -(k - 2)(k - 3) < m(G).
Similarly, under the conditions a = k - 1 > 3, the following relations hold:
k(k - , O,. , A , L ! , O. , l.^^/TA 1 i_2 , 51
m(G) -	—1 + 2a + bj + k - 1 + 3a + b < m(G) - -k2 + -k - 2 < m(G).
In both cases we get E(S, G) < m(G), which implies a(G) > |S| = |S'| + 2a + b = a(G') + 2a + b. By our inductive hypothesis, G' satisfies Conjecture 1.1. Consequently,
7t(G) < Yt(G') + 2a + b < a(G') + 2a + b +1 < a(G) + 1.
What remains is to establish the statement for k = 3 and a = k - 1=2. We consider two subcases. First, suppose that d(x) = 3. Denote the third neighbor of x outside K3 with y. If vertex y was a leaf, then we could exchange vertex x either with u2 or u2, and apply the proof for the case a = 1 = k - 2. Hence, we may assume that y is not a leaf, and therefore, graph G' = G - {x, u ', u ', u '', u2, u2, u2'} is not a trivial block graph. Also, m(G') = m(G) - 8. If D' is a minimum total dominating set of G', then D = D' U {u i, u 1, u2, u2} is a total dominating set of graph G, and hence Yt (G) < | D | = |D' | + 4 = Yt(G') + 4. Independently of whether y is inside S' ornotwehaveE (S',G) < E(S', G') +1 < m(G') +1 = m(G) -8 + 1 = m(G) -7. Let S = S'u{u', u'2', u2, u2'}. Then E(S,G) = E(S',G) + d(ui) + d«) + d(u2) + d(u2') < m(G) -7+2 +i + 2+1 = m(G) - 1, and we have a(G) > |S| = |S'| + 4 = a(G') + 4. Applying our inductive hypothesis to G', we have that Yt(G') < a(G') + 1. Therefore,
Yt(G) < Yt(G') +4 < a(G') + 5 < a(G) + 1.
Now, suppose that d(x) > 4. Let G' = G - {u i, u i, u'2', u2, u2, u2'}, and so m(G') = m(G) - 7. If D' is a minimum total dominating set of G', then D = D' U {u i, u i, u2, u2} is a total dominating set of G, and hence Yt(G) < |D| = |D'| + 4 = Yt(G) + 4. If x G S', the^(S',G) = E(S',G'). In this case, let S = S'u{u'2,u i',u2,u2'}. The^(S, G) = E(S', G) + d(u i) + d(u i') + d(u2) + d(u2') < m(G) - 7 + 2 + 1 2+1 = m(G) - 1, and we have a(G) > |S| = |S'| + 4 = a(G') + 4. Applying our inductive hypothesis to G', we have that Yt(G') < a(G') + 1. Therefore,
Yt(G) < Yt(G') +4 < a(G') + 5 < a(G) + 1.
If x G S', then E(S',G) = E(S',G') + 2 < m(G') + 2 = m(G) - 7 + 2 = m(G) - 5. In this case, let S = (S'\{x}) U {u b u'2, u i', u2, u2'}. Since d(x) > 4 we hav^(S, G) =
200
Ars Math. Contemp. 16 (2019) 245-255
£(S",G)-d(x)+d(wi)+d(ui)+d(ui')+d(u2)+d(u2') < m(G)-5-4+3+2+1+2+1 = m(G), implying that a(G) > |S| = |S+ 4 = a(G') + 4. Applying again our inductive hypothesis to G', we have that Yt(G') < a(G') + 1. Therefore,
Yt(G) < Yt(G') +4 < a(G') + 5 < a(G) + 1.
Case 2.3: h = 1.
We need to consider only one case which is shown in Figure 6. As we have already seen in Case 2.2, all other cases for h = 1 can be proved with the help of Lemma 2.1(ii) and 2.1(v).
Figure 6: The case for h = 1.
We may also suppose that there is at most one vertex in V(Kk)\{x} which has a path of length 1 attached to it. If we had more such vertices, then we would have adjacent support vertices and we could prove this case with Lemma 2.1(v). Denote this vertex with u and its child with v. There are also vertices in V(Kk)\{x} without a path attached to them. Denote them with w1;..., wk-2. Let G' = G — {u, v, w1;..., wk-2}, and so m(G') = m(G) — (fc(fc-1) + 1). If D' is a minimum total dominating set of G', then D = D' U{x,u} is a total dominating set of G,and hence Yt(G) < |D| = |D'| + 2 = Yt(G') + 2. Independently of whether x is inside S' or not we have J2 (S', G) < J2 (S', G') + k — 1 < m(G') + k — 1 = m(G) — (+ 1) + k — 1. Let S = S' U {v,w}. Then,
£(S, G) = ^(S', G) + d(v) + d(w)
< m(G) - f+ 1 ) + k - 1 + 1 + k - 1.
For k > 4, this gives
1 5
^(S, G) < m(G) - ^k2 + -k - 2 < m(G).
Hence, a(G) > |S| = |S'| + 2 = a(G') + 2 and applying our inductive hypothesis to G', we have that Yt(G') < a(G') + 1. Therefore,
Yt(G) < Yt(G') +2 < a(G') + 3 < a(G) + 1.
We end the proof with k = 3. In this case, x, u, v and w1 induce the paw graph and, by Lemma 2.5 and our inductive hypothesis, graph G satisfies (1.1).
We have considered all possible cases which can occur in a block graph which is neither
a tree nor a complete graph. Hence, Conjecture 1.1 is true over the family of block graphs.
□
2
Cs. Bujtas andM. Jakovac: Relating the total domination number and the annihilation ... 201
5 Concluding remarks
To show that our main results, namely Theorem 1.3 and 1.4, are sharp, we remark that trees are included in both classes. Therefore, we may refer to the family of trees characterized in [5] which satisfy Conjecture 1.1 with equality.
We may also observe that even cycles Cn, where n = 2 (mod 4), have Yt(Cn) = n + 1 and a(C„) = n. Also, there are other cactus graphs which are neither trees nor cycles, but satisfy Yt(G) = a(G) + 1. Take two vertex-disjoint cycles C6, and connect any vertex from the first cycle and any vertex from the second cycle with a path of length 3. We get a cactus graph G on n = 14 vertices and m =15 edges. It is easy to see that Yt (G) = 8 and a(G) = 7. Thus, Theorem 1.3 holds with equality for the graph G constructed this way. One can also use other cycles Cn with n = 2 (mod 4) and connect them with different paths to obtain other extremal examples. Hence, the following characterization problem remains open.
Problem 5.1. Characterize cactus graphs G which satisfy Yt(G) = a(G) + 1.
For block graphs, already the following question might be interesting.
Problem 5.2. Does there exist a block graph G which is neither a tree nor a K3 but satisfies
Yt(G) = a(G) + 1?
References
[1]	D. Archdeacon, J. Ellis-Monaghan, D. Fisher, D. Froncek, P. C. B. Lam, S. Seager, B. Wei and R. Yuster, Some remarks on domination, J. Graph Theory 46 (2004), 207-210, doi:10.1002/ jgt.20000.
[2]	B. Brimkov and I. V. Hicks, Memory efficient algorithms for cactus graphs and block graphs, Discrete Appl. Math. 216 (2017), 393-407, doi:10.1016/j.dam.2015.10.032.
[3]	V. Chvatal and C. McDiarmid, Small transversals in hypergraphs, Combinatorica 12 (1992), 19-26, doi:10.1007/bf01191201.
[4]	E. DeLaVina, Written on the Wall II, http://cms.dt.uh.edu/faculty/ delavinae/research/wowII/.
[5]	W. J. Desormeaux, T. W. Haynes and M. A. Henning, Relating the annihilation number and the total domination number of a tree, Discrete Appl. Math. 161 (2013), 349-354, doi:10.1016/j. dam.2012.09.006.
[6]	W. J. Desormeaux, M. A. Henning, D. F. Rall and A. Yeo, Relating the annihilation number and the 2-domination number of a tree, Discrete Math. 319 (2014), 15-23, doi:10.1016/j.disc. 2013.11.020.
[7]	J. R. Griggs and D. J. Kleitman, Independence and the Havel-Hakimi residue, Discrete Math. 127 (1994), 209-212, doi:10.1016/0012-365x(92)00479-b.
[8]	M. A. Henning, A survey of selected recent results on total domination in graphs, Discrete Math. 309 (2009), 32-63, doi:10.1016/j.disc.2007.12.044.
[9]	M. A. Henning and A. Yeo, Total Domination in Graphs, Springer Monographs in Mathematics, Springer, New York, 2013, doi:10.1007/978-1-4614-6525-6.
[10] J. Lyle and S. Patterson, A note on the annihilation number and 2-domination number of a tree, J. Comb Optim. 33 (2017), 968-976, doi:10.1007/s10878-016-0019-7.
202
Ars Math. Contemp. 16 (2019) 245-255
[11]	R. Pepper, On the annihilation number of a graph, in: V. Zafiris, M. Benavides, K. Gao, S. Hashemi, K. Jegdic, G. A. Kouzaev, P. Simeonov, L. Vladareanu and C. Vobach (eds.), AMATH'09 Proceedings of the 15th American Conference on Applied Mathematics, World Scientific and Engineering Academy and Society (WSEAS), Stevens Point, Wisconsin, USA, 2009 pp. 217-220, held in Houston, USA, April 30 - May 02, 2009.
[12]	R. D. Pepper, Binding Independence, Ph.D. thesis, University of Houston, Houston, Texas, 2004, https://search.proquest.com/docview/305196562.
[13]	S. Thomasse and A. Yeo, Total domination of graphs and small transversals of hypergraphs, Combinatorica 27 (2007), 473-487, doi:10.1007/s00493-007-2020-3.
[14]	Zs. Tuza, Covering all cliques of a graph, Discrete Math. 86 (1990), 117-126, doi:10.1016/ 0012-365x(90)90354-k.