| Title: | Guarded subgraphs and the domination game |
|---|
| Authors: | ID Brešar, Boštjan (Author)
ID Klavžar, Sandi (Author)
ID Košmrlj, Gašper (Author)
ID Rall, Douglas F. (Author) |
|---|
| Files: |  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
|
|---|
| Language: | English |
|---|
| Work type: | Scientific work |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | dominacijska igra, igralno dominacijsko številko, konveksni podgraf, (2-)izometrični podgraf |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Article acceptance date: | 08.06.2014 |
|---|
| Publication date: | 12.02.2015 |
|---|
| Publisher: | Discrete Mathematics & Theoretical Computer Science |
|---|
| Year of publishing: | 2015 |
|---|
| Number of pages: | Str. 161-168 |
|---|
| Numbering: | Letn. 17, št. 1 |
|---|
| PID: | 20.500.12556/DKUM-59258  |
|---|
| ISSN: | 1365-8050 |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 1365-8050 |
|---|
| COBISS.SI-ID: | 17273689 |
|---|
| NUK URN: | URN:SI:UM:DK:B52WXJ2D |
|---|
| Publication date in DKUM: | 10.07.2017 |
|---|
| Views: | 1683 |
|---|
| Downloads: | 261 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
