DIKUL - logo
(UL)
  • Set graphs. IV, Further connections with claw-freeness
    Milanič, Martin, 1980- ; Tomescu, Alexandru I.
    Graf ▫$G$▫ je graf množic, če dopušča aciklično usmeritev povezav, ki je tudi ekstenzionalna, kar pomeni, da so zunanje soseščine vozlišč grafa paroma različne. Ekvivalentno, grafi množic so temeljni ... grafi digrafovskih predstavitev hereditarno končnih množic, pri čemer pravimo, da je množica hereditarno končna, če je končna in ima za elemente samo hereditarno končne množice. Znano je, da je vsak povezan ▫$K_{1,3}$▫-prost graf (tj., graf brez krempljev) tudi graf množic in da je ekstenzionalno aciklično usmeritev takega grafa moč najti v polinomskem času. V članku posplošimo ta rezultat v tri različne smeri. Prvič, identificiramo največji hereditarni razred takih grafov ▫$G$▫, da za vsak povezan induciran podgraf ▫$H$▫ grafa ▫$G$▫ velja, da je ▫$H$▫ graf množic natanko tedaj, ko je brez krempljev. Drugič, obravnavamo grafe, v katerih nobena dva različna inducirana kremplja nimata sosednjih središč, in za ta razred grafov dokažemo, da lahko grafe množic ekvivalentno karakteriziramo z lastnostjo, povezano z zaporednim odstranjevanjem vozlišč. Nazadnje, za vsak ▫$r \geqslant 1$▫ pokažemo, da imajo povezani ▫$K_{1,r+2}$▫-prosti grafi aciklično orientacijo, ki je ▫$r$▫-ekstenzionalna, torej da ima lahko kvečjemu ▫$r$▫ različnih vozlišč isto zunanjo soseščino. Ta rezultat vodi tudi do preprostega algoritma linearne časovne zahtevnosti za iskanje ekstenzionalne aciklične orientacije danega povezanega grafa brez krempljev, kar izboljša prejšnji znani algoritem za ta problem.
    Vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 174, 2014, str. 113-121)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2014
    Jezik - angleški
    COBISS.SI-ID - 17070169

    Povezava(-e):

    http://dx.doi.org/10.1016/j.dam.2014.05.011

vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 174, 2014, str. 113-121)

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

Vnos na polico