402 KB51 KB200820252019Bujtás, CsillaJakovac, Markoštevilka:1letnik:16str. 183-202ISSN:1855-3966COBISSID_HOST:24318728URN:URN:NBN:SI:doc-68L993FAenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaannihilation numberblock graphbločni grafcactus graphindeks popolne prevladeindeks uničenjakaktusni graftotal domination numberRelating the total domination number and the annihilation number of cactus graphs and block graphs|The total domination number ?$\gamma_t(G)$? of a graph ?$G$? is the order of a smallest set ?$D \subseteq V(G)$? such that each vertex of ?$G$? is adjacent to some vertex in ?$D$?. The annihilation number ?$a(G)$? of ?$G$? is the largest integer ?$k$? such that there exist ?$k$? different vertices in ?$G$? with degree sum of at most ?$|E(G)|$?. It is conjectured that ?$\gamma_t(G) \leq a(G) + 1$? holds for every nontrivial connected graph ?$G$?. The conjecture was proved for graphs with minimum degree at least 3, and remains unresolved for graphs with minimum degree 1 or 2. In this paper we establish the conjecture for cactus graphs and block graphsIndeks popolne prevlade ?$\gamma_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 ?$\gamma_t(G) \leq 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 grafeTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije