VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Revisiting ▫$d$▫-distance (independent) domination in trees and in bipartite graphs
    Bujtás, Csilla ...
    V grafu ▫$G$▫ je ▫$d$▫-razdaljno ▫$p$▫-pakirno število ▫$\gamma_d^p(G)$▫ velikost najmanjše množice vozlišč grafa ▫$G$▫, ki je hkrati ▫$d$▫-razdaljno dominantna množica in ▫$p$▫-pakiranje. Leta 1994 ... sta Beineke in Henning postavila domnevo, da če je ▫$d\ge 1$▫ in ▫$T$▫ drevo reda ▫$n \geq d+1$▫, potem je ▫$\gamma_d^1(T) \leq \frac{n}{d+1}$▫. Domnevo sta podprla z dokazom za ▫$d\in \{1,2,3\}$▫. V tem članku je dokazano, da ▫$\gamma_d^1(G) \leq \frac{n}{d+1}$▫ velja za vsak dvodelni graf ▫$G$▫ reda ▫$n \geq d+1$▫ in za vsak ▫$d\ge 1$▫. Karakterizirana so drevesa ▫$T$▫, za katera velja ▫$\gamma_d^1(T) = \frac{n}{d+1}$▫. Dokazano je tudi, da če ima ▫$T$▫ ▫$\ell$▫ listov, potem velja ▫$\gamma_d^1(T) \leq \frac{n-\ell}{d}$▫ (pod pogojem, da je ▫$n-\ell \geq d$▫) in ▫$\gamma_d^1(T) \leq \frac{n+\ell}{d+2}$▫ (pod pogojem, da je ▫$n\geq d$▫). Slednji rezultat razširja Favaronov izrek iz leta 1992, ki trdi, da je ▫$\gamma_1^1(T) \leq \frac{n+\ell}{3}$▫. V obeh primerih so karakterizirana drevesa, ki dosežejo enakost, izpeljani so tudi ustrezni zaključki za ▫$d$▫-razdaljno dominantno število dreves.
    Vir: Discrete mathematics. - ISSN 0012-365X (Vol. 349, iss. 6, [article no.] 114972, Jun. 2026, 11 str.)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2026
    Jezik - angleški
    COBISS.SI-ID - 263511811

    Povezava(-e):

    https://www.sciencedirect.com/science/article/pii/S0012365X25005801
    DiRROS - Digitalni repozitorij raziskovalnih organizacij Slovenije
    Repozitorij Univerze v Ljubljani – RUL
    DOI

vir: Discrete mathematics. - ISSN 0012-365X (Vol. 349, iss. 6, [article no.] 114972, Jun. 2026, 11 str.)
loading ...
loading ...
loading ...

Vnos na polico