DIKUL - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
PDF
  • A note on bipartite graphs whose ▫$[1,k]$▫-domination number equal to their number of vertices
    Ghareghani, Narges ; Peterin, Iztok ; Sharifani, Pouyeh
    Podmnožici ▫$D$▫ množice vozlišč ▫$V$▫ grafa ▫$G$▫ rečemo ▫$[1,k]$▫-dominacijska množica, če je vsako vozlišče iz množice ▫$V-D$▫ sosednje vsaj enemu in največ ▫$k$▫ vozliščem iz ▫$D$▫. Če ima ... ▫$[1,k]$▫-dominacijska množica najmanjšo možno moč, potem ji rečemo ▫$\gamma_{[1,k]}$▫-množica, njena moč pa je ▫$[1,k]$▫-dominacijsko število ▫$\gamma_{[1,k]}(G)$▫ grafa ▫$G$▫. V tem prispevku pokažemo, da je odločitveni problem ali je ▫$\gamma_{[1,k]}(G)=|V|$▫ NP-težek problem celo za dvodelne grafe. Konstruiramo tudi dvodelen graf ▫$G$▫ na ▫$n$▫ vozliščih, za katerega velja ▫$\gamma_{[1,k]}(G)=n$▫, kjer je ▫$n$▫ poljubno naravno število, ki ustreza pogoju ▫$n\geq (k+1)(2k+3)$▫.
    Vir: Rocznik Akademii Górniczo-Hutniczej im. Stanisława Staszica. Opuscula Mathematica. - ISSN 1232-9274 (Vol. 40, no. 3, 2020, str. 375-382)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2020
    Jezik - angleški
    COBISS.SI-ID - 18961497

    Povezava(-e):

    https://doi.org/10.7494/OpMath.2020.40.3.375
    https://www.opuscula.agh.edu.pl/vol40/3/art/opuscula_math_4020.pdf
    DOI

Vnos na polico