¿^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 18 (2020) 359-369
https://doi.org/10.26493/1855-3974.1950.8bd
(Also available at http://amc-journal.eu)
On an annihilation number conjecture*
Vadim E. Levitf ©
Department of Computer Science, Ariel University, Ariel, Israel
Eugen Mandrescu ©
Department of Computer Science, Holon Institute of Technology, Holon, Israel
Received 13 March 2019, accepted 26 May 2020, published online 23 October 2020
Abstract
Let a(G) denote the cardinality of a maximum independent set, while G) be the size of a maximum matching in the graph G = (V, E). If a(G) + p(G) = |V|, then
G is a Konig-Egervary graph. If d1 < d2 < ■ ■ ■ < dn is the degree sequence of G, then the annihilation number a (G) of G is the largest integer k such that J2i=i dj < |E|. A set A C V satisfying J2veA deg(v) < |E| is an annihilation set; if, in addition, deg (x) +J2veA deg(v) > |E|, for every vertex x G V(G) - A, then A is a maximal annihilation set in G.
In 2011, Larson and Pepper conjectured that the following assertions are equivalent:
(i)	a (G) = a (G);
(ii)	G is a Konig-Egervary graph and every maximum independent set is a maximal annihilating set.
It turns out that the implication "(i) (ii)" is correct.
In this paper, we show that the opposite direction is not valid, by providing a series of generic counterexamples.
Keywords: Maximum independent set, maximum matching, Konig-Egervary graph, annihilation set, annihilation number.
Math. Subj. Class. (2020): 05C69, 05C07
*The authors express their thanks to the anonymous referees, who suggested a number of comments that led to a better exposition of the manuscript. t Corresponding author.
E-mail addresses: levitv@ariel.ac.il (Vadim E. Levit), eugeLm@hit.ac.il (Eugen Mandrescu) ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
169
Ars Math. Contemp. 18 (2020) 187-210
1 Introduction
Throughout this paper G = (V, E) is a finite, undirected, loopless graph without multiple edges, with vertex set V = V(G) of cardinality | V (G) | = n (G), and edge set E = E(G) of size |E (G)| = m (G). If X c V(G), then G[X] is the subgraph of G induced by X .By G - v we mean the subgraph G[V (G) - {v}], for v e V (G). K„, Km,„, P„, C„ denote respectively, the complete graph on n > 1 vertices, the complete bipartite graph on m, n > 1 vertices, the path on n > 1 vertices, and the cycle on n > 3 vertices, respectively.
The disjoint union of the graphs Gi, G2 is the graph Gx U G2 having the disjoint union of V(Gx), V(G2) as a vertex set, and the disjoint union of E(Gx), E(G2) as an edge set. In particular, nG denotes the disjoint union of n > 1 copies of the graph G.
A set S C V(G) is independent if no two vertices from S are adjacent, and by Ind(G) we mean the family of all the independent sets of G. An independent set of maximum size is a maximum independent set of G, and a(G) = max{|S| : S e Ind(G)}. Let Q(G) denote the family of all maximum independent sets.
A matching in a graph G is a set of edges M C E(G) such that no two edges of M share a common vertex. A matching of maximum cardinality ^(G) is a maximum matching, and a perfect matching is one saturating all vertices of G.
It is known that |_n (G) /2J +1 < a(G) + ^(G) < n (G) < a(G) + 2^(G) hold for every graph G [ ]. If a(G) + ^(G) = n (G), then G is called a Konig-Egervary graph [11, 36]. For instance, each bipartite graph is a Konig-Egervary graph [13, 20]. Various properties of Konig-Egervary graphs can be found in [3,4, 5,16, 17, 18,21, 22, 23, 25, 26, 27, 28,29, 30,31,35].
Let dx < d2 < • • • < dn be the degree sequence of a graph G. Pepper [33, 34] defined the annihilation number of G, denoted a (G), to be the largest integer k such that the sum of the first k terms of the degree sequence is at most half the sum of the degrees in the sequence. In other words, a (G) is precisely the largest integer k such that J2i=i d < m (G).
Clearly, a (G) = n (G) if and only if m (G) = 0. If m (G) = 1, then a (G) = n (G) - 1. The converse is not true; e.g., the graph Kx,p has a (Kx,p) = m (Kx,p) = p = n (Kx,p) - 1, while p may be greater than one.
For A C V(G), let deg(A) =	deg(v). Every A C V (G) satisfying deg(A) <
m (G) is an annihilating set. Clearly, every independent set is annihilating. An annihilating set A is maximal if deg(A U {x}) > m (G), for every vertex x e V(G) - A, and it is maximum if |A| = a (G) [33]. For example, if G = Kp,q = (A, B, E) andp > q, then A is a maximum annihilating set, while B is a maximal annihilating set.
Theorem 1.1 ([33]). For every graph G,
a (G) > max
n (G)
,a (G)
For instance,
a (C7) = a (C7) =
a
(K2,3) = a (K2,3) >
- (C7) 2
n (K2,3) 2
while a (C6) =
(P5) =3 > a (P5) = n (C6
2
n (P5
> a (C^ .
2
a
2
V. E. Levit and E. Mandrescu: On an annihilation number conjecture
361
The relation between the annihilation number and various parameters of a graph were studied in [1, 2, 7, 8, 9, 10, 12, 14, 15, 19, 32, 33].
Theorem 1.2 ([24]). For a graph G with a (G) > n2)' a (G) = a (G) if and only ifG is a Konig-Egervary graph and every S e Q(G) is a maximum annihilating set.
All the maximum independent sets of the cycle C5 are maximum annihilating. Moreover, a (C5) = a (C5). Nevertheless, C5 is not a Konig-Egervary graph. In other words, the condition a (G) > n(G) in Theorem 1.2 is necessary.
Actually, Larson and Pepper [24] proved a stronger result that reads as follows.
Theorem 1.3. Let G be a graph with a (G) > ^¿p. Then the following are equivalent:
(i)	a (G) = a (G);
(ii)	G is a Konig-Egervary graph and every S e Q(G) is a maximum annihilating set;
(iii)	G is a Konig-Egervary graph and some S e Q(G) is a maximum annihilating set.
Along these lines, it was conjectured that the impacts of maximum and maximal annihilating sets are the same.
Conjecture 1.4 ([24]). Let G be a graph with a (G) > ^^. Then the following assertions are equivalent:
(i)	a (G) = a (G);
(ii)	G is a Konig-Egervary graph and every S e Q(G) is a maximal annihilating set.
One can easily infer that every maximum annihilating set is also a maximal annihilating set, since the sum of the a +1 smallest entries from the degree sequence D = (d\ < d2 < ■ ■ ■ < dn) is greater than m (G), then the same is true for every a +1 entries of D. Thus the "(i) (ii)" part of Conjecture 1.4 is valid, in accordance with Theorem 1.2.
Consider the graphs from Figure 1. The graph H1 has a (Hi) > a (Hi) and none of its maximum independent sets is a maximal or a maximum annihilating set. The graph H2 has a (H2) = a (H2) and each of its maximum independent sets is both a maximal and a maximum annihilating set. Notice that a (Hi) > , while a (H2) < 2).
Consider the graphs from Figure 2. The graph Gi has a (Gi) = < a (Gi) and each of its maximum independent sets is neither a maximal nor a maximum annihilating set. The graph G2 has a (G2) = a (G2) = n(22), every of its maximum independent sets is both a maximal and a maximum annihilating set, and it has a maximal independent set that is a maximal non-maximum annihilating set, namely {u, v}. The graph G3 has a (G3) = a (G3) > n(23) and every of its maximum independent sets is both a maximal
171
Ars Math. Contemp. 18 (2020) 187-210
Gl	G2	G3	G4
Idkl 132 Ni^/t
Figure 2: König-Egervary graphs with a (G1) = a (G3) =4, a (G2) = 3, a (G4) = 6.
and a maximum annihilating set. The graph G4 has a (G4) > a (G4) > 4) and none of its maximum independent sets is a maximal or a maximum annihilating set.
In this paper we invalidate the "(ii) (i)" part of Conjecture 1.4, by providing some generic counterexamples. Let us notice that, if G is a Konig-Egervary graph, and H = qK1 U G, then H inherits this property. Moreover, the relationship between the independence numbers and annihilation numbers of G and H remains the same, because a (H) = a (G) + q and a (H) = a (G) + q. Therefore, it is enough to construct only connected counterexamples. Finally, we prove that Conjecture 1.4 is true for graphs with independence number equal to three.
2 An infinite family of counterexamples
In what follows, we present a series of counterexamples to the opposite direction of Conjecture 1.4. All these graphs have unique maximum independent sets.
Lemma 2.1. The graph Hk, k > 0, from Figure 3 is a connected Konig-Egervâry graph that has a unique maximum independent set, namely, Sk = {xk,..., xi, a4, a3, a2, ai}, where = Hk — {xj, yj : j = 1, 2,..., k} and S0 = {a4, a3, a2, a1}.
k + 4 k + 4 k + 4 k + 4 k + 3 k + 2 k + 3 Xk	Xk-i	xi	a4	a3	a2	ai
Hk
yk yk-i yi	64	63	62	61
k + 5 k + 6 k + 6 k + 6 k + 5 k + 2 k + 2
Figure 3: Hk is a Konig-Egervary graph with a (Hk) = k + 4, k > 0.
Proof. Notice that the graph Hk from Figure 3 can be defined as follows:
V (Hk) = V (Kk+4,k+4) = {xi,yi : i = 1,..., k} U {«1,02,03, 04} U {61, 62,63,64} , E (Hk) = E (Kk+4,k+4) U {ykyk-i,... ,y2yi,yi64,6463} - {0361 ,«262,0261, 0162} .
Clearly, Sk = {xk,..., x1, a4, a3, a2, a1} is an independent set and
{xjyj : j = 1, 2, ..., k} U {0464, 0362, 0363, 0161}
is a perfect matching of Hk. Hence, we get
|Vk| = 2M (Hk) = |Sk| + M (Hk) < a (Hk) + m (Hk) < |Vk|,
V. E. Levit and E. Mandrescu: On an annihilation number conjecture
361
which implies a (Hk) + M (Hk) = |Vk i.e., Hk is a Konig-Egervary graph, and a (Hk) k + 4= |Sfc |.
Let Lk = Hk [Xk U Yk ], k > 1, and L0 = Hk [A U B], where
Xk = {xj : j = 1,..., k} , A = {01,02,03,04} and
Yk = {yj : j = 1,..., k} , B = {61,62,63,64} .
Since Lk has, on the one hand, Kk,k as a subgraph, and, on the other hand,
ykyk-i, Vk-iVk-2,..., y2yi e E (Lfc),
it follows that Xk is the unique maximum independent set of Lk. The graph L0 has A as a unique independent set, because
Cg + 6364 = (A U B, {0164,6402, 0263,6303, 0362,6204, 0461,6ioi, 6364})
has A as a unique maximum independent set, and L0 can be obtained from Cg + 6364 by adding a number of edges.
Since Hk can be obtained from the union of Lk and L0 by adding some edges, and Sk = Xk U A is independent in Hk, it follows that Hk has Sk as a unique maximum independent set.	□
Corollary 2.2. The graph Gk, k > 0, from Figure 4 is a connected König-Egerväry graph that has a unique independent set, namely, Sk = {xj : i = 1,..., k} U {0^ : i = 1,..., 5}, where G0 = Gk — {xj, yj : j = 1, 2,..., k} and S0 = {0j : i = 1,..., 5}.
k + 4
Xk
k + 4
05
k + 3
04
k + 2
03
k+3 02
k+2 01
Gk
yk k + 6
yk-i k + 7
y1 k+7
64 k+7
63 k+6
62 k+2
61 k+2
Figure 4: Gk is a König-Egervary graph with a (Gk) = k + 5, k > 0.
Proof. Notice that the graph Gk from Figure 4 can be defined as follows:
V (Gk) = V (Kk+5,k+4)
= jxj, yi : i = 1, .. ., k} U joi, 02, 03, 04, 05} U {61, 62, 63, 64} , E (Gk) = E (Kk+4,k+4) U jykyk-i,..., y2yi, yib4,6463}
- {0362, 0361,0262, 0162,0161} .
According to Lemma 2.1, Gk - 01 is a Konig-Egervary graph with a unique maximum independent set, namely, Wk = jxi : i = 1,..., k} U {0i : i = 1,..., 4}. Since Sk = Wk U {01} is an independent set and ^ (Gk) = ^ (Gk - 01) = k + 4, it follows that Gk is a Konig-Egervary graph and Sk is its unique maximum independent set.	□
173
Ars Math. Contemp. 18 (2020) 187-210
Theorem 2.3. For every k > 0, there exists a connected non-bipartite Konig-Egervary graph Hk = (Vk, Ek), of order 2k + 8, satisfying the following:
•	a (Hk) > ^ = a (Hk),
•	each S G Q (Hk) is a maximal annihilating set.
Proof. Let Hk = (Vk, Ek), k > 0, be the graph from Figure 3 (in the bottom and the top lines are written the degrees of its vertices), where H0 = Hk - {xi,..., xk, ..., yk }. Clearly, every Hk is non-bipartite.
By Lemma 2.1, each Hk, k > 0, is a Konig-Egervary graph with a unique maximum independent set, namely, Sk = {xk,..., x1, a4, a3, a2, a1}, where S0 = {a4, a3, a2, a1}.
Case 1. k = 0. Since m (H0) = 13 and the degree sequence (2,2,2,3, 3,4,5,5), we infer that a (H0) = 5 > 4 = a (H0). In addition, deg (S0) = m (H0) - 1, i.e., each maximum independent set of H0 is a maximal non-maximum annihilating set.
Case 2. k > 1. Clearly, Hk has m (Gk) = k2 + 9k +13 and its degree sequence is
k + 2, k + 2, k + 2, k + 3, k + 3, k + 4,..., k + 4, k + 5, k + 5, k + 6,..., k + 6.
"-V-'	"-V-'
k+1 k
Since the sum of the first k + 6 degrees of the sequence satisfies
k2 + 10k +16 > m (Hk),
we infer that the annihilation number a (Hk) < k + 6. The sum 12 + 4 (x — 5) + kx of the first x > 5 degrees of the sequence satisfies 12 + 4 (x — 5) + kx < m (Hk) for x < k2+9+k4+21. This implies
a (Hfc)
k2 +9k + 21 k + 4
k + 5 > k + 4 = a (Hk),
i.e., has no maximum annihilating set belonging to Q (Hk). Since its unique maximum independent set = jai, a2, a3, a4, xi, x2,..., xk} has
deg (Sfc) = k2 + 8k + 12 < m (Hk),
while
deg (Sk) + minjdeg (v) : v e Vk - S} = (k2 + 8k +12) + (k + 2) > m (Hk),
we infer that Sk is a maximal annihilating set.	□
Theorem 2.4. For every k > 0, there exists a connected non-bipartite Konig-Egervary graph Gk = (Vk, Ek), of order 2k + 9, satisfying the following:
•	a (Gk) > [^ j = a (Gk),
•	each S e Q (Gk) is a maximal annihilating set.
V. E. Levit and E. Mandrescu: On an annihilation number conjecture
361
Proof. Let Gk = (Vk, Ek), k > 1, be the graph from Figure 4 (in the bottom and the top lines are written the degrees of its vertices), and G0 = Gk - jxi,..., xk, yi,..., yk}.
Corollary 2.2 claims that Gk, k > 0, is a Konig-Egervary graph with a unique maximum independent set, namely Sk = {x1,..., xk, a1,..., a5} , k > 1, and S0 = ja1,...,
0,5}.
Case 1. The non-bipartite Konig-Egervary graph G0 has m (G0) = 15 and the degree sequence (2,2, 2, 2,3,3,4, 6, 6). Hence, 0 (G0) = 6 > 5 = a (G0). In addition, Q (G0) = {S0}, and deg (S0) = 14, i.e., each maximum independent set of G0 is a maximal nonmaximum annihilating set.
Case 2. k > 1. Clearly, Gk has m (Gk ) = k2 + 10k + 15 and its degree sequence is
k + 2, k + 2, k + 2, k + 2, k + 3, k + 3, k + 4,..., k + 4, k + 6, k + 6, k + 7,..., k + 7.
"-V-'	"-V-'
k+1 k
Since the sum of the first k + 7 degrees of the sequence satisfies
k2 + 11k +18 > m (Gk),
we infer that the annihilation number 0 (Gk) < k + 6. The sum 14 + 4 (x — 5) + kx of the first x > 6 degrees of the sequence satisfies 14 + 4 (x — 6) + kx < m (Gk) for
x < k2+k1+k4+25. This implies
k2 + 10k + 25
a (Gk )
k+4
k + 6 > k + 5 = a (Gk),
i.e., Gk has no maximum annihilating set belonging to Q (Gk ). Since its unique maximum independent set Sk has
deg (Sk ) = k2 + 9k +14 < m (Gk),
while
deg (Sk) + min{deg (v) : v G Vk — Sk} = (k2 + 9k +14) + (k + 2) > m (Gk), we infer that Sk is a maximal annihilating set.	□
3 Conclusions
If G is a Konig-Egervary graph with a (G) G {1, 2}, then a (G) = a (G) and each maximum independent set is maximal annihilating, since the list of such Konig-Egervary graphs reads as follows:
{K1, K2, K1 U K1, K1 U K2, K2 U K2, P3, P4, C4, K3 + e, K4 — e} .
Consequently, Conjecture 1.4 is correct for Konig-Egervary graphs with a (G) < 2. Let G be a disconnected Konig-Egervary graph with a (G) = 3.
• If a (G) = a (G), then
3K1, 2K1 U K2, K1 U 2K2,3K2, K1 U P3, K1 U P4,
G G \ K1 U C4, K1 U (K3 + e), K1 U (K4 — e), K2 U P3, K2 U C4 while every S G Q (G) is a maximal annihilating set.
175
Ars Math. Contemp. 18 (2020) 187-210
Gi
G2
M
Figure 5: Gi = K3 + e and G2 = K4 — e.
• If a (G) < a (G), then G e {K2 U P4, K2 U (K3 + e), K2 U (K4 - e)}, while for every such G, there exists a maximum independent set, which is a not a maximal annihilating set. Moreover, for K2 U (K3 + e) and K2 U (K4 — e) all maximum independent sets are not maximal annihilating.
Thus Conjecture 1.4 is true for disconnected Konig-Egervary graphs with a (G) = 3.
We have already mentioned in Introduction that the "(i) (ii)" part of Conjecture 1.4 is true.
Proposition 3.1. Let G be a graph with a (G) > . If G
is a connected Konig-Egervary graph with a (G) = 3, and every S e Q(G) is a maximal annihilating set, then a (G) = a (G).
Proof. In Figure 6 we present all connected Konig-Egervary graphs with a (G) = 3 having n(G) e {4, 5}. For these graphs a (G) = a (G), which means that Conjecture 1.4 is true.
Gi
G3
^/I	G5
G7
G2

G4
G«
Gg
Figure 6: Konig-Egervary graphs with a (G) = 3 = a (G) and n(G) < 5.
Now, we may assume that n(G) = 6, since a (G) > ^ (G) holds for each Konig-Egervary graph.
Let d\ < d2 < ■ ■ ■ < d6 be the degree sequence of G.
It is known that a (G) < a (G) (Theorem 1.1). Thus we have only three cases with
3 = a (G) < a (G) to cover, namely, a (G) e {4, 5, 6}.
Case 1. a (G) = 4. Then, by definition, di + d2 + d3 + d4 < m (G) < d5 + d6 and di + d2 + d3 + d4 + d5 > m (G) > dg.
Let q be the number of edges in G joining the vertices v5, v6 with the vertices vi,v2, v3,v4. At least two vertices from the set {vi, v2, v3, v4} must be joined by an edge, otherwise, a (G) > 4 > 3. Assume that v3v4 e E (G). Hence, v5v6 e E (G), otherwise,
¿5 + d6 = q < q + 2 < di + d,2 + d,3 + ¿4,
V. E. Levit and E. Mandrescu: On an annihilation number conjecture
361
in contradiction with d1 + d2 + d3 + d4 < d5 + d6. Similarly, there are no more edges but v3v4 joining vertices from the set {v^ v2, v3, v4}, otherwise
d5 + de — q + 2 < q + 4 < di + d2 + d3 + d4,
in contradiction with d1 + d2 + d3 + d4 < d5 + d6. Therefore, {v1, v2, v3} is a maximum independent set of G, since a (G) — 3. On the other hand, {vi, v2, v3} is not a maximal
annihilating set, because d1 + d2 + d3 + d4 < m (G).
Case 2. a (G) — 5. By definition, it follows that d1 + d2 + d3 + d4 + d5 < m (G) < d6. Hence, the set {v1, v2, v3, v4, v5} is independent, in contradiction with the fact that
a (G) — 3.
Case 3. a (G) — 6. This means that G has no edges, which is not possible, because
a (G) — 3.	□
To complete the picture, Theorems 2.3 and 2.4 present various counterexamples to the "(ii) —^ (i)" part of Conjecture 1.4 for every independence number greater than three. Our intuition tells us that the real obstacle for the "(i) —^ (ii)" part Conjecture 1.4 not to be true is the size of the annihilation number. It motivates the following.
Conjecture 3.2. If G is a Konig-Egervâry graph with a (G) > 4n (G), and every S G Q(G) is a maximal annihilating set, then a (G) — a (G).
ORCID iDs
Vadim E. Levit !> https://orcid.org/0000-0002-4190-7050 Eugen Mandrescu © https://orcid.org/0000-0003-3533-9728
References
[1]	J. Amjadi, An upper bound on the double domination number of trees, Kragujevac J. Math. 39 (2015), 133-139, doi:10.5937/kgjmath1502133a.
[2]	H. Aram, R. Khoeilar, S. M. Sheikholeslami and L. Volkmann, Relating the annihilation number and the Roman domination number, Acta Math. Univ. Comenian. (N.S.) 87 (2018), 1-13, http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/ article/view/4 71.
[3]	I. Beckenbach and R. Borndorfer, Hall's and Konig's theorem in graphs and hypergraphs, Discrete Math. 341 (2018), 2753-2761, doi:10.1016/j.disc.2018.06.013.
[4]	A. Bhattacharya, A. Mondal and T. S. Murthy, Problems on matchings and independent sets of a graph, Discrete Math. 341 (2018), 1561-1572, doi:10.1016/j.disc.2018.02.021.
[5]	F. Bonomo, M. C. Dourado, G. Duran, L. Faria, L. N. Grippo and M. D. Safe, Forbidden subgraphs and the Konig-Egervary property, Discrete Appl. Math. 161 (2013), 2380-2388, doi:10.1016/j.dam.2013.04.020.
[6]	E. Boros, M. C. Golumbic and V. E. Levit, On the number of vertices belonging to all maximum stable sets of a graph, Discrete Appl. Math. 124 (2002), 17-25, doi:10.1016/s0166-218x(01) 00327-4.
[7]	C. Bujtas and M. Jakovac, Relating the total domination number and the annihilation number of cactus graphs and block graphs, Ars Math. Contemp. 16 (2019), 183-202, doi:10.26493/ 1855-3974.1378.11d.
177
Ars Math. Contemp. 18 (2020) 187-210
[8]	N. Dehgardi, S. Norouzian and S. M. Sheikholeslami, Bounding the domination number of a tree in terms of its annihilation number, Trans. Comb. 2 (2013), 9-16, doi:10.22108/toc.2013. 2652.
[9]	N. Dehgardi, S. M. Sheikholeslami and A. Khodkar, Bounding the rainbow domination number of a tree in terms of its annihilation number, Trans. Comb. 2 (2013), 21-32, doi:10.22108/toc. 2013.3051.
[10]	N. Dehgardi, S. M. Sheikholeslami and A. Khodkar, Bounding the paired-domination number of a tree in terms of its annihilation number, Filomat 28 (2014), 523-529, doi:10.2298/ fil1403523d.
[11]	R. W. Deming, Independence numbers of graphs—an extension of the Koenig-Egervary theorem, Discrete Math 27 (1979), 23-33, doi:10.1016/0012-365x(79)90066-9.
[12]	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.
[13]	E. Egervary, On combinatorial properties of matrices (in Hungarian), Mat. Lapok 38 (1931), 16-28.
[14]	M. Gentner, M. A. Henning and D. Rautenbach, Smallest domination number and largest independence number of graphs and forests with given degree sequence, J. Graph Theory 88 (2018), 131-145, doi:10.1002/jgt.22189.
[15]	M. Jakovac, Relating the annihilation number and the 2-domination number of block graphs, Discrete Appl. Math. 260 (2019), 178-187, doi:10.1016/j.dam.2019.01.020.
[16]	A. Jarden, V. E. Levit and E. Mandrescu, Two more characterizations of Konig-Egervary graphs, Discrete Appl. Math. 231 (2017), 175-180, doi:10.1016/j.dam.2016.05.012.
[17]	A. Jarden, V. E. Levit and E. Mandrescu, Critical and maximum independent sets of a graph, Discrete Appl. Math. 247 (2018), 127-134, doi:10.1016/j.dam.2018.03.058.
[18]	A. Jarden, V. E. Levit and E. Mandrescu, Monotonic properties of collections of maximum independent sets of a graph, Order 36 (2019), 199-207, doi:10.1007/s11083-018-9461-8.
[19]	D. A. Jaumea and G. Molina, Maximum and minimum nullity of a tree degree sequence, 2018, arXiv:1806.02399 [math.CO].
[20]	D. Konig, Graphen und Matrizen, Mat. Lapok 38 (1931), 116-119.
[21]	E. Korach, T. Nguyen and B. Peis, Subgraph characterization of red/blue-split graph and Konig Egervary graphs, in: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2006 pp. 842-850, doi:10.1145/1109557.1109650, held in Miami, FL, January 22 - 24, 2006.
[22]	C. E. Larson, A note on critical independence reductions, Bull. Inst. Combin. Appl. 51 (2007), 34-46.
[23]	C. E. Larson, The critical independence number and an independence decomposition, European J. Combin. 32 (2011), 294-300, doi:10.1016/j.ejc.2010.10.004.
[24]	C. E. Larson and R. Pepper, Graphs with equal independence and annihilation numbers, Electron. J. Combin. 18 (2011), #P180 (9 pages), doi:10.37236/667.
[25]	V. E. Levit and E. Mandrescu, Combinatorial properties of the family of maximum stable sets of agraph, Discrete Appl. Math. 117 (2002), 149-161, doi:10.1016/s0166-218x(01)00183-4.
[26]	V. E. Levit and E. Mandrescu, On a+ -stable Konig-Egervary graphs, Discrete Math. 263 (2003), 179-190, doi:10.1016/s0012-365x(02)00528-9.
V. E. Levit and E. Mandrescu: On an annihilation number conjecture
361
[27]	V. E. Levit and E. Mandrescu, Critical independent sets and Konig-Egervary graphs, Graphs Combin. 28 (2012), 243-250, doi:10.1007/s00373-011-1037-y.
[28]	V. E. Levit and E. Mandrescu, Vertices belonging to all critical sets of a graph, SIAMJ. Discrete Math. 26 (2012), 399-403, doi:10.1137/110823560.
[29]	V. E. Levit and E. Mandrescu, On maximum matchings in Konig-Egervary graphs, Discrete Appl. Math 161 (2013), 1635-1638, doi:10.1016/j.dam.2013.01.005.
[30]	V. E. Levit and E. Mandrescu, A set and collection lemma, Electron. J. Combin. 21 (2014), #P1.40 (8 pages), doi:10.37236/2514.
[31]	V. E. Levit and E. Mandrescu, On Konig-Egervary collections of maximum critical independent sets, Art Discrete Appl. Math. 2 (2019), #P1.02 (9 pages), doi:10.26493/2590-9770.1261.9a0.
[32]	W. Ning, M. Lu and K. Wang, Bounding the locating-total domination number of a tree in terms of its annihilation number, Discuss. Math. Graph Theory 39 (2019), 31-40, doi:10.7151/ dmgt.2063.
[33]	R. D. Pepper, Binding Independence, Ph.D. thesis, University of Houston, 2004, https: //www.proquest.com/docview/30 519 65 62.
[34]	R. D. 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, 2009 pp. 217-220.
[35]	T. Short, On some conjectures concerning critical independent sets of a graph, Electron. J. Combin. 23 (2016), #P2.43 (10 pages), doi:10.37236/5580.
[36]	F. Sterboul, A characterization of the graphs in which the transversal number equals the matching number, J. Comb. Theory Ser. B 27 (1979), 228-229, doi:10.1016/0095-8956(79)90085-6.