VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • The ▫$d$▫-distance ▫$p$▫-packing domination number: complexity, cycles, and trees
    Bujtás, Csilla ...
    Množica vozlišč ▫$X\subseteq V(G)$▫ je ▫$d$▫-razdaljna dominantna množica, če za vsak ▫$u\in V(G)\setminus X$▫ obstaja ▫$x\in X$▫, tako da je ▫$d(u,x) \le d$▫, in ▫$X$▫ je ▫$p$▫-pakiranje, če je ... ▫$d(u,v) \ge p+1$▫ za vsaka različna ▫$u,v\in X$▫. Za graf ▫$G$▫ je ▫$d$▫-razdaljno ▫$p$▫-pakirno število ▫$\gamma_d^p(G)$▫ minimalna velikost množice vozlišč ▫$G$▫, ki je hkrati ▫$d$▫-razdaljo dominantna množica in ▫$p$▫-pakiranje. Dokazano je, da je za vsako dve fiksni celo števili ▫$d$▫ in ▫$p$▫ z ▫$2 \le d$▫ in ▫$0 \le p \leq 2d-1$▫ odločitveni problem, ali velja ▫$\gamma_d^p(G) \leq k$▫, NP-poln za dvodelne ravninske grafe. Dobili smo potrebni in zadostni pogoj za obstoj ▫$d$▫-razdaljno ▫$p$▫-pakirne domninantne množice v ▫$C_n$▫ in določili ▫$\gamma_d^p(C_n)$▫ za vsak ▫$d$▫, ▫$p$▫ in ▫$n$▫. Za drevo ▫$T$▫ na ▫$n$▫ vozliščih z ▫$\ell$▫ listi in ▫$s$▫ podpornimi vozlišči je dokazano, da (i) ▫$\gamma_2^0(T) \geq \frac{n-\ell-s+4}{5}$▫, (ii) ▫$\left \lceil \frac{n-\ ell-s+4}{5} \right \rceil \leq \gamma_2^2(T) \leq \left \lfloor \frac{n+3s-1}{5} \right \rfloor$▫, in če je ▫$d \geq 2$▫, potem (iii) ▫$\gamma_d^2(T) \leq \frac{n-2\sqrt{n}+d+1}{d}$▫. Neenakost (i) izboljša prejšnjo mejo, ki so jo določili Meierling in Volkmann ter neodvisno od njih Raczek, Lemańska in Cyman, medtem ko (iii) razširja prejšnji rezultat za ▫$\gamma_2^2(T)$▫, ki ga je določil Henning. V večini primerov je obravnavana in ugotovljena natančnost neenakosti. Dokazano je tudi, da vsak povezan graf ▫$G$▫ vsebuje vpeto drevo ▫$T$▫, tako da velja ▫$\gamma_2^2(T) \leq \gamma_2^2(G)$▫.
    Vir: Aequationes mathematicae. - ISSN 0001-9054 (Vol. 100, iss. 2, article no. 25, Apr. 2026, 22 str.)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2026
    Jezik - angleški
    COBISS.SI-ID - 269190659

    Povezava(-e):

    https://link.springer.com/article/10.1007/s00010-026-01266-w
    Repozitorij Univerze v Ljubljani – RUL
    DiRROS - Digitalni repozitorij raziskovalnih organizacij Slovenije
    DOI

vir: Aequationes mathematicae. - ISSN 0001-9054 (Vol. 100, iss. 2, article no. 25, Apr. 2026, 22 str.)
loading ...
loading ...
loading ...

Vnos na polico