Relating the total domination number and the annihilation number of cactus graphs and block graphs - Bujtás, Csilla (Ars mathematica contemporanea, 2019)
Indeks popolne prevlade ?$γ_t(G)$? grafa ?$G$? je red najmanjše množice ?$D \subseteq V(G)$?, za katero velja, da je vsako vozlišče grafa ?$G$? sosedno kakšnemu vozlišču grafa ?$D$?. Indeks uničenja ?$a(G)$? grafa ?$G$? je največje celo število ?$k$?, za katerega obstaja ?$k$? različnih vozlišč v ?$G$?, ki ustrezajo pogoju, da je vsota njihovih stopenj največ ?$|E(G)|$?. Domneva se, da neenakost ?$γ_t(G) ≤ a(G) + 1$? velja za vsak netrivialen povezan graf ?$G$?. Ta domneva je bila dokazana za grafe, pri katerih je minimalna stopnja njihovih vozlišč najmanj 3, njen status pa ostaja nerazrešen za grafe, pri katerih je minimalna stopnja njihovih vozlišč 1 ali 2. V članku potrdimo njeno veljavnost za kaktusne grafe in bločne grafe.
Keywords: annihilation number; block graph; bločni graf; cactus graph; indeks popolne prevlade; indeks uničenja; kaktusni graf; total domination number