Akademska digitalna zbirka SLovenije - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Spreading in graphs
    Brešar, Boštjan ...
    Raziskovanih je bilo več konceptov, ki modelirajo procese razširjanja (informacij, bolezni, predmetov itd.) v grafih ali omrežjih. V mnogih kontekstih predpostavljamo, da so pred začetkom procesa ... nekatera vozlišča grafa ▫$G$▫ kontaminirana. Po pravilu ▫$q$▫-prisile kontaminirano vozlišče, ki ima največ ▫$q$▫ nekontaminiranih sosedov, prisili vse sosede, da postanejo kontaminirani, medtem ko po pravilu ▫$p$▫-pronicanja nekontaminirano vozlišče postane kontaminirano, če je vsaj ▫$p$▫ njegovih sosedov kontaminiranih. Če postanejo glede na podano množico ▫$S$▫ začetno kontaminiranih vozlišč vsa vozlišča na koncu kontaminirana, po kontinuirani uporabi pravila ▫$q$▫-prisile (oziroma pravilo ▫$p$▫-pronicanja), se ▫$S$▫ imenuje množica ▫$q$▫-prisile (oziroma množica ▫$p$▫-pronicanja) v ▫$G$▫. V tem članku obravnavamo množice ▫$S$▫, ki so hkrati množice ▫$q$▫-prisile in ▫$p$▫-pronicanja in jih imenujemo množice ▫$(p,q)$▫-razširjanja. Za dani pozitivni celi števili ▫$p$▫ in ▫$q$▫ je minimalna kardinalnost množice ▫$(p,q)$▫-razširjanja v ▫$G$▫ število ▫$(p,q)$▫-razširjanja grafa ▫$G$▫ in jo označimo s ▫$\sigma_{(p,q)}(G)$▫. Čeprav so bile množice ▫$q$▫-prisile obravnavane v desetinah člankov, odločitvena različica ustrezne grafovske invariante ni bila obravnavana prej, zato zapolnimo to vrzel z dokazom njene NP-polnosti. To nam omogoča dokazati NP-polnost odločitvene različice števila ▫$(p,q)$▫-razširjanja v grafih za poljubna ▫$p$▫ in ▫$q$▫. Ponovno, za vsak ▫$p\in {\mathbb N}$▫ in ▫$q\in {\mathbb N}\cup{\infty}$▫ najdemo algoritem linearne časovne zahtevnosti za določanje števila ▫$(p,q)$▫-razširjanja poljubnega drevesa, kjer v primeru ▫$p\ge 2$▫ uporabimo Riedlov algoritem iz [Largest and smallest minimal percolating sets in trees, Electron. J. Combin. 19 (2012) Paper 64] o ▫$p$▫-pronicanju v drevesih. Poleg tega predstavimo spodnjo in zgornjo mejo za število ▫$(p,q)$▫-razširjanja drevesa ter karakteriziramo ekstremne družine dreves. V primeru kvadratnih mrež združimo nekaj rezultatov Bollobáša iz [The Art of Mathematics: Coffee Time in Memphis. Cambridge Univ. Press, New York, 2006] in delovne skupine AIM Minimum Rank-Special Graphs Work Group iz [Zero forcing sets and the minimum rank of graphs, Linear algebra Appl. 428 (2008) 1628-1648] z novimi rezultati o ▫$(2,1)$▫-razširjanju in ▫$(4,q)$▫-razširjanju, da dobimo ▫$\sigma_{(p,q)}(P_m\Box P_n)$▫ za vse ▫$(p,q)\in ({\mathbb N}\setminus{3})\times ({\mathbb N}\cup{\infty})$▫ in vse ▫$m,n \in {\mathbb N}$▫.
    Vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 353, Aug. 2024, str. 139-150)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2024
    Jezik - angleški
    COBISS.SI-ID - 195071235

    Povezava(-e):

    https://www.sciencedirect.com/science/article/pii/S0166218X24001707
    DOI

Vnos na polico