| Naslov: | Domination game critical graphs |
|---|
| Avtorji: | ID Bujtás, Csilla (Avtor)
ID Klavžar, Sandi (Avtor)
ID Košmrlj, Gašper (Avtor) |
|---|
| Datoteke: |  Discussiones_Mathematicae_Graph_Theory_2015_Bujtas,_Klavzar,_Kosmrlj_Domination_game_critical_graphs.pdf (194,74 KB)
MD5: F52741DC9E1C4954DB3E246A85FD7EC7
 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1839
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Znanstveno delo |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FNM - Fakulteta za naravoslovje in matematiko
|
|---|
| Opis: | The domination game is played on a graph ▫$G$▫ by two players who alternately take turns by choosing a vertex such that in each turn at least one previously undominated vertex is dominated. The game is over when each vertex becomes dominated. One of the players, namely Dominator, wants to finish the game as soon as possible, while the other one wants to delay the end. The number of turns when Dominator starts the game on ▫$G$▫ and both players play optimally is the graph invariant ▫$\gamma_g(G)$▫, named the game domination number. Here we study the ▫$\gamma_g$▫-critical graphs which are critical with respect to vertex predomination. Besides proving some general properties, we characterize ▫$\gamma_g$▫-critical graphs with ▫$\gamma_g =2$▫ and with ▫$\gamma_g =3$▫, moreover for each ▫$n$▫ we identify the (infinite) class of all ▫$\gamma_g$▫-critical ones among the ▫$n$▫th powers ▫$C_N^n$▫ of cycles. Along the way we determine ▫$\gamma_g(C_N^n)$▫ for all ▫$n$▫ and ▫$N$▫. Results of a computer search for ▫$\gamma_g$▫-critical trees are presented and several problems and research directions are also listed. |
|---|
| Ključne besede: | domination game, domination game critical graphs, powers of cycles, trees |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Poslano v recenzijo: | 31.08.2024 |
|---|
| Datum sprejetja članka: | 20.02.2025 |
|---|
| Datum objave: | 28.02.2025 |
|---|
| Št. strani: | str. 781-796 |
|---|
| Številčenje: | Letn. 35, št. 4 |
|---|
| PID: | 20.500.12556/DKUM-65335  |
|---|
| ISSN: | 1234-3099 |
|---|
| UDK: | 519.17 |
|---|
| COBISS.SI-ID: | 17464921 |
|---|
| ISSN pri članku: | 1234-3099 |
|---|
| NUK URN: | URN:SI:UM:DK:D0MNDQWR |
|---|
| Datum objave v DKUM: | 31.03.2017 |
|---|
| Število ogledov: | 1405 |
|---|
| Število prenosov: | 438 |
|---|
| 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. |
