On an annihilation number conjecture - Levit, Vadim E. (Ars mathematica contemporanea, 2020)
Naj ?$α(G)$? označuje moč maksimalne neodvisne množice, ?$μ(G)$? pa velikost maksimalnega prirejanja v grafu ?$G=(V, E)$?. Če je ?$α(G)+μ(G)=|V|$?, potem je ?$G$? König-Egerváryjev graf. Če je ?$d_1 ≤ d_2 ≤ … ≤ d_n$? stopenjsko zaporedje grafa ?$G$?, potem je prag ?$a(G)$? grafa ?$G$? največje celo število ?$k$?, pri katerem je ?$\sum_{i=1}^{k}d_i ≤ |E|$?. Množica ?$A\subseteq V$?, ki zadošča pogoju? $\sum_{v\in A} \text{deg}(v)≤ |E|$?, se imenuje množica s pragom; če velja poleg tega ?$\text{deg}(x) +\sum_{v\in A} \text{deg}(v)>|E|$? za vsako točko ?$x\in V(G)-A$?, potem je ?$A$? maksimalna množica s pragom v ?$G$?. Leta 2011 sta Larson in Pepper postavila domnevo o enakovrednosti naslednjih trditev: (i) ?$α(G) =a(G)$?; (ii) ?$G$? je König-Egerváryjev graf in vsaka maksimalna neodvisna množica je maksimalna množica s pragom. Izkazalo se je, da je implikacija"(i) ?$\Longrightarrow$? (ii)" pravilna. V članku dokažemo, da obratna implikacija ne velja, prikažemo pa tudi vrsto generičnih protiprimerov.
Keywords: annihilation number; annihilation set; König-Egerváry graph; König-Egerváryjev graf; maksimalna neodvisna množica; maksimalno prirejanje; maximum independent set; maximum matching; množica s pragom; prag