-
Dominating sequences in graphsBrešar, Boštjan ...Zaporedje vozlišč v grafu ▫$G$▫ se imenuje legalno dominacijsko zaporedje, če vsako vozlišče v zaporedju dominira vsaj eno vozlišče, ki ni dominirano z vozlišči pred njim in so na koncu vsa vozlišča ... grafa ▫$G$▫ dominirana. Dolžina najkrajšega takšnega zaporedja je znana kot dominantno število grafa, v tem članku pa obravnavamo legalna dominacijska zaporedja največje dolžine, ki jo imenujemo Grundyjevo dominantno število grafa ▫$G$▫. Dokažemo, da ima vsak graf legalna dominacijska zaporedja vseh možnih dolžin med njegovim dominantnim številom in Grundyjevim dominantnim številom in okarakteriziramo grafe, pri katerih sta dominantno in Grundyjevo dominantno število oba enaka ▫$k$▫, za ▫$k \le 3$▫. Dokažemo tudi, da je odločitvena verzija Grundyjevega dominantnega števila NP-poln problem, celo ko ga obravnavamo na tetivnih grafih in predstavimo linearen algoritem za določitev tega števila na drevesih, kografih in razcepljenih grafih. Več rezultatov posplošimo v kontekst pokritij s povezavami v hipergrafih.Vir: Discrete mathematics. - ISSN 0012-365X (Vol. 336, 2014, str. 22-36)Vrsta gradiva - članek, sestavni delLeto - 2014Jezik - angleškiCOBISS.SI-ID - 17114457
Avtor
Brešar, Boštjan |
Dravec, Tanja |
Milanič, Martin, 1980- |
Rall, Douglas F. |
Rizzi, Romeo
Teme
matematika |
teorija grafov |
grafovska dominacija |
pokritje s povezavami |
hipergraf |
drevo |
razcepljeni graf |
Grundyjevo dominantno število |
mathematics |
graph theory |
graph domination |
edge cover |
hypergraph |
tree |
split graph |
Grundy domination number
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Brešar, Boštjan | 17005 |
Dravec, Tanja | 32028 |
Milanič, Martin, 1980- | 30211 |
Rall, Douglas F. | |
Rizzi, Romeo |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.