DIKUL - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • Best possible upper bounds on the restrained domination number of cubic graphs
    Brešar, Boštjan ; Henning, Michael A.
    Dominacijska množica grafa ▫$G$▫ je taka množica vozlišč, da je vsako vozlišče iz množice ▫$V(G) \setminus S$▫ sosednje s kakim vozliščem iz množice ▫$S$▫. Zamejena dominacijska množica grafa ▫$G$▫ ... je dominacijska množica z dodatno omejitvijo, da graf ▫$G-S$▫, ki ga dobimo iz grafa ▫$G$▫ z odstranitvijo vseh vozlišč iz ▫$S$▫, nima izoliranih vozlišč. Dominacijsko število ▫$\gamma(G)$▫ (oz. zamejeno dominacijsko število ▫$\gamma_r(G)$▫) je najmanjša moč dominacijske (oz. zamejene dominacijske) množice v grafu ▫$G$▫. Naj bo ▫$G$▫ kubičen graf reda ▫$n$▫. Klasičen rezultat, ki ga je dokazal Reed [Combin. Probab. Comput. 5 (1996), 277-295] pravi, da je ▫$\gamma(G) \le \frac{3}{8}n$▫ in ta meja je najboljša možna. Določitev najboljše možne meje za zamejeno dominacijsko število grafa ▫$G$▫ je večji izziv, in v tem članku dokažemo, da velja ▫$\gamma_{r}(G) \le \frac{2}{5}n$▫.
    Vir: Journal of graph theory. - ISSN 0364-9024 (Vol. 106, iss. 4, Aug. 2024, str. 763–815)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2024
    Jezik - angleški
    COBISS.SI-ID - 199137795

    Povezava(-e):

    https://onlinelibrary.wiley.com/doi/10.1002/jgt.23095
    DiRROS - Digitalni repozitorij raziskovalnih organizacij Slovenije
    DOI

vir: Journal of graph theory. - ISSN 0364-9024 (Vol. 106, iss. 4, Aug. 2024, str. 763–815)

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

Vnos na polico