How long can one bluff in the domination game?

Brešar, Boštjan; Dorbec, Paul; Klavžar, Sandi; Košmrlj, Gašper

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	How long can one bluff in the domination game?
Avtorji:	ID Brešar, Boštjan (Avtor) ID Dorbec, Paul (Avtor) ID Klavžar, Sandi (Avtor) ID Košmrlj, Gašper (Avtor)
Datoteke:	Discussiones_Mathematicae_Graph_Theory_2017_Bresar_et_al._How_long_can_one_bluff_in_the_domination_game.pdf (56,60 KB) MD5: E2E21DDAD32086F0B202FAFD568E19EF http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1899
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 an arbitrary graph $G$ by two players, Dominator and Staller. The game is called Game 1 when Dominator starts it, and Game 2 otherwise. In this paper bluff graphs are introduced as the graphs in which every vertex is an optimal start vertex in Game 1 as well as in Game 2. It is proved that every minus graph (a graph in which Game 2 finishes faster than Game 1) is a bluff graph. A non-trivial infinite family of minus (and hence bluff) graphs is established. Minus graphs with game domination number equal to 3 are characterized. Double bluff graphs are also introduced and it is proved that Kneser graphs $K(n,2)$ , za $n \ge 6$ , are double bluff. The domination game is also studied on generalized Petersen graphs and on Hamming graphs. Several generalized Petersen graphs that are bluff graphs but not vertex-transitive are found. It is proved that Hamming graphs are not double bluff.
Ključne besede:	domination game, game domination number, bluff graphs, minus graphs, generalized Petersen graphs, Kneser graphs, Cartesian product of graphs, Hamming graphs
Status publikacije:	Objavljeno
Verzija publikacije:	Objavljena publikacija
Leto izida:	2017
Št. strani:	str. 337-352
Številčenje:	Letn. 37, št. 2
PID:	20.500.12556/DKUM-65601
ISSN:	1234-3099
UDK:	519.17
COBISS.SI-ID:	17978457
DOI:	10.7151/dmgt.1899
ISSN pri članku:	1234-3099
NUK URN:	URN:SI:UM:DK:DMQJPGXS
Datum objave v DKUM:	09.05.2017
Število ogledov:	1348
Število prenosov:	464
Metapodatki:
Področja:	Ostalo
:	BREŠAR, Boštjan, DORBEC, Paul, KLAVŽAR, Sandi in KOŠMRLJ, Gašper, 2017, How long can one bluff in the domination game? Discussiones mathematicae : Graph theory [na spletu]. 2017. Vol. 37, no. 2, p. 337–352. [Dostopano 29 april 2025]. DOI 10.7151/dmgt.1899. Pridobljeno s: https://dk.um.si/IzpisGradiva.php?lang=slv&id=65601 Kopiraj citat

Skupna ocena:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Iščem podobna dela... Prosim, počakajte...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:	Discussiones mathematicae : Graph theory
Skrajšan naslov:	Discuss. Math., Graph Theory
Založnik:	Technical University Press
ISSN:	1234-3099
COBISS.SI-ID:	7487065

Licence

Licenca:	CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna

Povezava:	http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
Opis:	Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.
Začetek licenciranja:	09.05.2017

Sekundarni jezik

Jezik:	Slovenski jezik
Naslov:	Kako dolgo se lahko pretvarjamo v dominacijski igri?
Opis:	Dominacijsko igro na grafu $G$ igrata dva igralca, Dominator in Zavlačevalka. Ko igro začenja Dominator, ji rečemo Igra 1, sicer pa Igra 2. V članku vpeljemo grafe pretvarjanja kot tiste grafe, v katerih je vsako vozlišče optimalno začetno vozlišče za Igro 1 in tudi za Igro 2. V tem članku je dokazano, da je vsak minus graf (to je graf, v katerem se Igra 2 konča hitreje kot Igra 1) tudi graf pretvarjanja. Predstavimo netrivialno neskončno družine minus grafov (in s tem tudi grafov pretvarjanja). Minus grafi z igralnim dominantnim številom enakim 3 so okarakterizirani. Vpeljemo tudi grafe dvojnega pretvarjanja in dokažemo, da so med njimi Kneserjevi grafi, $K(n,2)$ , za $n \ge 6$ . Dominacijsko igro obravnavamo tudi v posplošenih Petersenovih grafih in Hammingovih grafih. Odkrijemo več posplošenih Petersenovih grafov, ki so grafi pretvarjanja, niso pa vozliščno tranzitivni. Dokažemo, da Hammingov grafi niso grafi dvojnega pretvarjanja.
Ključne besede:	dominacijska igra, igralno dominantno število, grafi pretvarjanja, minus grafi, posplošeni Petersenovi grafi, Kneserjevi grafi, kartezični produkt grafov, Hammingovi grafi

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj