On an annihilation number conjecture

angleški

2020

letnik 18, številka 2

König-Egerváryjev graf   maksimalna neodvisna množica   maksimalno prirejanje   množica s pragom   prag

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Naj ?$\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 protiprimerov.

28.04.2021