271 KB24 KB200820252020Levit, Vadim E.Mandrescu, Eugenletnik:18številka:2str. 359-369ISSN:1855-3966COBISSID_HOST:42128899URN:URN:NBN:SI:doc-JVVHZ0TMenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaannihilation numberannihilation setKönig-Egerváry graphKönig-Egerváryjev grafmaksimalna neodvisna množicamaksimalno prirejanjemaximum independent setmaximum matchingmnožica s pragompragOn an annihilation number conjecture|Let ?$\alpha(G)$? denote the cardinality of a maximum independent set, while ?$\mu(G)$? be the size of a maximum matching in the graph ?$G=(V, E)$?. If ?$\alpha(G)+\mu(G)=|V|$?, then ?$G$? is a König-Egerváry graph. If ?$d_1 \leq d_2 \leq \cdots \leq d_n$? is the degree sequence of ?$G$?, then the annihilation number ?$a(G)$? of ?$G$? is the largest integer ?$k$? such that ?$\sum_{i=1}^{k}d_i \leq |E|$?. A set ?$A\subseteq V$? satisfying ?$\sum_{v\in A} \text{deg}(v)\leq |E|$? is an annihilation set, if, in addition, ?$\text{deg}(x) +\sum_{v\in A} \text{deg}(v)>|E|$?, for every vertex ?$x\in 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) ?$\alpha(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) ?$\Longrightarrow$? (ii)" is correct. In this paper, we show that the opposite direction is not valid, by providing a series of generic counterexamplesNaj ?$\alpha(G)$? označuje moč maksimalne neodvisne množice, ?$\mu(G)$? pa velikost maksimalnega prirejanja v grafu ?$G=(V, E)$?. Če je ?$\alpha(G)+\mu(G)=|V|$?, potem je ?$G$? König-Egerváryjev graf. Če je ?$d_1 \leq d_2 \leq \cdots \leq 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 \leq |E|$?. Množica ?$A\subseteq V$?, ki zadošča pogoju? $\sum_{v\in A} \text{deg}(v)\leq |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) ?$\alpha(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 protiprimerovTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije