DIKUL - logo
(UL)
  • Domination parameters with number 2 : interrelations and algorithmic consequences
    Bonomo, Flavia ...
    V članku obravnavamo najosnovnejše dominacijske invariante grafov, v katerih se število ▫$2$▫ pojavlja kot ključen del definicije. Klasificiramo jih glede na tri kriterije, od katerih dva porajata že ... prej raziskovane invariante: šibko ▫$2$▫-dominantno število, ▫$\gamma\,\!\!_{w\!\!\:2}(G)$▫, ▫$2$▫-dominantno število, ▫$\gamma_2(G)$▫, ▫$\{2\}$▫-dominantno število, ▫$\gamma_{\{2\}}(G)$▫, dvojno dominantno število, ▫$\gamma\,\!\!_{{\scriptstyle \times} \! 2}(G)$▫, celotno ▫$\{2\}$▫-dominantno število, ▫$\gamma\;\!\!_{t{\{2\}}}$▫, in celotno dvojno dominantno število, ▫$\gamma\;\!\!_{t\!{\scriptstyle \times} \! 2}$▫, kjer je ▫$G$▫ graph, v katerem je ustrezna invarianta dobro definirana. Tretji kriterij poraja mavrične različice omenjenih šestih parametrov, med katerimi je ena mavrična različica že bila dobra raziskana, tri druge pa porajajo zanimive parametre. Skupaj s posebno, obširno raziskovano Rimsko dominacijo, ▫$\gamma_R(G)$▫, in dvema klasičnima parametroma, dominantnim številom, ▫$\gamma(G)$▫, in celotnim dominantnim številom, ▫$\gamma_t(G)$▫, obravnavamo 13 dominacijskih invariant grafa ▫$G$▫. V glavnem rezultatu članka predstavimo ostre spodnje in zgornje meje za vsako od invariant, izražene z vsako drugo invarianto, katerih večina predstavlja nove rezultate, ki jih dokažemo v tem članku. Kot posledica glavnega izreka dobimo nove rezultate o obstoju aproksimacijskih algoritmov obravnavanih invariant, ki jih povežemo z ostrimi ali skoraj ostrimi mejami neaproksimabilnosti, ki veljajo celo v razredu razcepljenih grafov.
    Vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 235, Jan. 2018, str. 23-50)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2018
    Jezik - angleški
    COBISS.SI-ID - 18192985

    Povezava(-e):

    http://doi.org/10.1016/j.dam.2017.08.017

vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 235, Jan. 2018, str. 23-50)

loading ...
loading ...
loading ...

Vnos na polico