Geodesic
On an annihilation number conjecture
Ars Mathematica Contemporanea, Tome 18 (2020) no. 2, pp. 359-369.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

Let α(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 α(G) + μ(G) = |V|, then G is a König-Egerváry 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 sumi = 1k di ≤ |E|. A set A ⊆ V satisfying ∑v ∈ Adeg (v) ≤ |E| is an annihilation set; if, in addition, deg (x) + ∑v ∈ Adeg (v) > |E|, for every vertex x ∈ 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) α(G) = a(G);(ii) G is a König-Egerváry 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.
DOI : 10.26493/1855-3974.1950.8bd
Keywords: Maximum independent set, matching, tree, bipartite graph, König-Egerváry graph, annihilation set, annihilation number 
@article{10_26493_1855_3974_1950_8bd,
     author = {Vadim E. Levit and Eugen Mandrescu},
     title = {On an annihilation number conjecture},
     journal = {Ars Mathematica Contemporanea},
     pages = {359--369},
     publisher = {mathdoc},
     volume = {18},
     number = {2},
     year = {2020},
     doi = {10.26493/1855-3974.1950.8bd},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1950.8bd/}
}
TY  - JOUR
AU  - Vadim E. Levit
AU  - Eugen Mandrescu
TI  - On an annihilation number conjecture
JO  - Ars Mathematica Contemporanea
PY  - 2020
SP  - 359
EP  - 369
VL  - 18
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1950.8bd/
DO  - 10.26493/1855-3974.1950.8bd
LA  - en
ID  - 10_26493_1855_3974_1950_8bd
ER  - 
%0 Journal Article
%A Vadim E. Levit
%A Eugen Mandrescu
%T On an annihilation number conjecture
%J Ars Mathematica Contemporanea
%D 2020
%P 359-369
%V 18
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1950.8bd/
%R 10.26493/1855-3974.1950.8bd
%G en
%F 10_26493_1855_3974_1950_8bd
Vadim E. Levit; Eugen Mandrescu. On an annihilation number conjecture. Ars Mathematica Contemporanea, Tome 18 (2020) no. 2, pp. 359-369. doi : 10.26493/1855-3974.1950.8bd. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1950.8bd/

Cité par Sources :