VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Total dominating sequences in graphs
    Brešar, Boštjan ; Henning, Michael A. ; Rall, Douglas F.
    Vozlišče grafa celotno dominira drugo vozlišče, če je z njim sosednje. Zaporedje vozlišč grafa ▫$G$▫ se imenuje celotno dominacijsko zaporedje, če vsako vozlišče ▫$v$▫ v zaporedju celotno dominira ... vsaj eno vozlišče, ki še ni bilo celotno dominirano pred pojavitvijo vozlišča ▫$v$▫ v zaporedju in so na koncu vsa vozlišča grafa ▫$G$▫ celotno dominirana. Dolžina najkrajšega takšnega zaporedja je dominantno število grafa ▫$G$▫, v tem članku pa obravnavamo celotna dominacijska zaporedja največje dolžine, ki jo imenujemo Grundyjevo celotno dominantno število grafa ▫$G$▫ in označimo z ▫$\gamma_{\mathrm{gr}}^t(G)$▫. V članku okarakteriziramo grafe ▫$G$▫, za katere je ▫$\gamma_{\mathrm{gr}}^t(G) = | V(G) |$▫ in tiste, za katere je ▫$\gamma_{\mathrm{gr}}^t(G) = 2$▫. Za netrivialna drevesa ▫$T$▫ reda ▫$n$▫, v katerih nobeno vozlišče nima v soseščini več kot en list, dokažemo neenakost ▫$\gamma_{\mathrm{gr}}^t(T) \geq \frac{2}{3}(n + 1)$▫ in opišemo pripadajoča ekstremalna drevesa. Dokažemo tudi, da za povezan ▫$k$▫-regularen graf ▫$G$▫ reda ▫$n$▫, kjer je ▫$k \ge 3$▫ in je graf različen od ▫$K_{k, k}$▫, velja ▫$\gamma_{\mathrm{gr}}^t(G) \geq(n + \lceil \frac{k}{2} \rceil - 2) /(k - 1)$▫, če graf ▫$G$▫ ni dvodelen in ▫$\gamma_{\mathrm{gr}}^t(G) \geq(n + 2 \lceil \frac{k}{2} \rceil - 4) /(k - 1)$▫, če je graf ▫$G$▫ dvodelen. Dokažemo tudi, da je Grundyjevo celotno dominantno število omejeno navzgor z dvakratnikom Grundyjevega dominantnega števila, medtem ko je lahko od tega števila tudi manjše za poljubno vrednost. Na koncu predstavimo naravno povezavo med zaporedji povezavnih pokritij v hipergrafih, ki pripelje tudi do rezultata o NP-polnosti odločitvene različice Grundyjevega celotnega dominantnega števila.
    Vir: Discrete mathematics. - ISSN 0012-365X (Vol. 339, iss. 6, 2016, str. 1665-1676)
    Vrsta gradiva - članek, sestavni del
    Leto - 2016
    Jezik - angleški
    COBISS.SI-ID - 17670233

    Povezava(-e):

    http://dx.doi.org/10.1016/j.disc.2016.01.017

vir: Discrete mathematics. - ISSN 0012-365X (Vol. 339, iss. 6, 2016, str. 1665-1676)
loading ...
loading ...
loading ...

Vnos na polico