| Naslov: | Guarded subgraphs and the domination game |
|---|
| Avtorji: | ID Brešar, Boštjan (Avtor)
ID Klavžar, Sandi (Avtor)
ID Košmrlj, Gašper (Avtor)
ID Rall, Douglas F. (Avtor) |
|---|
| Datoteke: |  Discrete_Mathematics_&_Theoretical_Computer_Science_2015_Bresar_et_al._Guarded_subgraphs_and_the_domination_game.pdf (690,85 KB)
MD5: 644B1ECC1DD7E3BDDE818323DE99332E
 http://dmtcs.episciences.org/2123
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Znanstveno delo |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FNM - Fakulteta za naravoslovje in matematiko
|
|---|
| Opis: | V članku vpeljemo koncept zaščitenega podgrafa. Množica le-teh po definicji leži med množico konveksnih in 2-izometričnih podgrafov, hkrati pa ni primerljiva z množico izometričnimih podgrafov. Dokažemo nekatere metrične lastnosti zaščitenih podgrafov ter koncept uporabimo v dominacijski igri, v kateri dva igralca, Dominator in Zavlačevalka, izmenično izbirata vozlišča grafa, tako da vsako izbrano vozlišče poveča množico dominiranih vozlišč. Dominatorjev cilj je končati igro, tj. dominirati celoten graf, čim hitreje, medtem ko je Zavlačevalkin cilj odigrati čim več potez. Igralno dominacijsko število je število potez v igri, ko Dominator začne in oba igralca igrata optimalno. Kot glavni rezultat članka dokažemo, da igralno dominacijsko število grafa ni nikoli manjše, kot igralno dominacijsko število njegovega zaščitenega podgrafa. Predstavljenih je tudi več aplikacij tega rezultata. |
|---|
| Ključne besede: | dominacijska igra, igralno dominacijsko številko, konveksni podgraf, (2-)izometrični podgraf |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum sprejetja članka: | 08.06.2014 |
|---|
| Datum objave: | 12.02.2015 |
|---|
| Založnik: | Discrete Mathematics & Theoretical Computer Science |
|---|
| Leto izida: | 2015 |
|---|
| Št. strani: | Str. 161-168 |
|---|
| Številčenje: | Letn. 17, št. 1 |
|---|
| PID: | 20.500.12556/DKUM-59258  |
|---|
| ISSN: | 1365-8050 |
|---|
| UDK: | 519.17 |
|---|
| COBISS.SI-ID: | 17273689 |
|---|
| ISSN pri članku: | 1365-8050 |
|---|
| NUK URN: | URN:SI:UM:DK:B52WXJ2D |
|---|
| Datum objave v DKUM: | 10.07.2017 |
|---|
| Število ogledov: | 1685 |
|---|
| Število prenosov: | 261 |
|---|
| Metapodatki: |    |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
