1. How long can one bluff in the domination game?Boštjan Brešar, Paul Dorbec, Sandi Klavžar, Gašper Košmrlj, 2017, izvirni znanstveni članek 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
Objavljeno v DKUM: 09.05.2017; Ogledov: 1348; Prenosov: 451
 Celotno besedilo (56,60 KB)
Gradivo ima več datotek! Več... |
2. Domination game: extremal families of graphs for 3/5-conjecturesBoštjan Brešar, Sandi Klavžar, Gašper Košmrlj, Douglas F. Rall, 2013, izvirni znanstveni članek Opis: Igralca, Dominator in Zavlačevalka, izmenoma izbirata vozlišča grafa ▫$G$▫, takoda vsako izbrano vozlišče poveča množico do sedaj dominiranih vozlišč. Cilj Dominatorja je končati igro čim hitreje, medtem ko je Zavlačevalkin cilj ravno nasprotno. Igralno dominacijsko število ▫$gamma_g(G)$▫ je skupno število izbranih vozlišč v igri, ko Dominator naredi prvo potezo in oba igralca igrata optimalno. Postavljena je bila domneva [W.B. Kinnersley, D.B. West, R. Zemani, Extremal problems for game domination number, Manuscript, 2012], da velja ▫$gamma_g(G) leq frac{3|V(G)|}{5}$▫ za poljuben graf ▫$G$▫ brez izoliranih vozlišč. V posebnem je domneva odprta tudi, ko je ▫$G$▫ gozd. V tem članku predstavimo konstrukcije, ki nam dajo velike družine dreves, ki dosežejo domnevno mejo ▫$3/5$▫. Leplenje dreves iz nekaterih izmed teh družin napoljuben graf nam da konstrukcijo grafov ▫$G$▫, ki imajo igralno dominacijsko število enako ▫$3|V(G)|/5$▫. Z računalnikom smo poiskali vsa ekstremna drevesa znajveč 20 vozlišči. V posebnem, na 20 vozliščih obstaja natanko deset dreves ▫$T$▫, za katere velja ▫$gamma_g(T) = 12$▫, in vsa pripadajo skonstruiranim družinam.
Ključne besede: matematika, teorija grafov, dominacijska igra, igralno dominacijsko številko, 3/5-domneva, računalniško iskanje, mathematics, graph theory, domination game, game domination number, 3/5-conjecture, computer search
Objavljeno v DKUM: 10.07.2015; Ogledov: 1488; Prenosov: 95
 Povezava na celotno besedilo |
3. Domination game played on trees and spanning subgraphsBoštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2013, izvirni znanstveni članek Opis: Igra dominacije na grafu ▫$G$▫ je bila vpeljana v [B. Brešar, S. Klavžar, D. F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979-991]. Dva igralca, Dominator in Zavlačevalec, drug za drugim izbirata po eno vozlišče grafa. Vsako izbrano vozlišče mora povečati množico vozlišč, ki so bila dominirana do tega trenutka igre. Oba igralca izbirata optimalno strategijo, pri čemer Dominator želi igro končati v najmanjšem možnem številu korakov, Zavlačevalec pa v največjem možnem številu korakov. Igralno dominacijsko število ▫$gamma_g(G)$▫ je število izbranih vozlišč v igri, kjer je Dominator prvi izbral vozlišče. Ustrezno invarianto, ko igro začne Zavlačevalec, označimo z ▫$gamma_g'(G)$▫. V članku sta obe igri proučevani na drevesih in vpetih podgrafih. Dokazana je spodnja meja za igralno dominacijsko število drevesa, ki je funkcija njegovega reda in maksimalne stopnje. Pokazano je, da je meja asimptotično optimalna. Dokazano je, da za vsak ▫$k$▫ obstaja drevo ▫$T$▫ z ▫$(gamma_g(T),gamma_g'(T)) = (k,k+1)$▫ in postavljena je domneva, da ne obstaja drevo z ▫$(gamma_g(T),gamma_g'(T)) = (k,k-1)$▫. Obravnavana je povezava med igralnim dominacijskim številom grafa in njegovimi vpetimi podgrafi. Dokazano je, da obstajajo 3-povezani grafi ▫$G$▫, ki vsebujejo 2-povezani vpeti podgraf ▫$H$▫, tako da je igralno dominacijsko število grafa ▫$H$▫ poljubno manjše od igralnega dominacijskega števila grafa ▫$G$▫. Podobno je dokazano, da za vsako celo število ▫$ell ge 1$▫ obstajata graf ▫$G$▫ in njegov vpeti podgraf $T$, tako da velja ▫$gamma_g(G)-gamma_g(T) ge ell$▫. Po drugi strani obstajajo grafi ▫$G$▫, za katere je igralno dominacijsko število vsakega vpetega drevesa v ▫$G$▫ poljubno večje od igralnega dominacijskega števila od ▫$G$▫.
Ključne besede: igra dominacije, igralno dominacijsko število, drevo, vpeti podgraf, graph theory, domination game, game domination number, tree, spanning subgraph
Objavljeno v DKUM: 10.07.2015; Ogledov: 1349; Prenosov: 93
Povezava na celotno besedilo |
4. Domination gameBoštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2009 Opis: The domination game played on a graph ▫$G$▫ consists of two players, Dominator and Staller who alternate taking turns choosing a vertex from ▫$G$▫ such that whenever a vertex is chosen the graph in as few steps as possible and Staller wishes to delay the process as much as possible. The game domination number ▫$gamma_g(G)$▫ is the number of vertices chosen when Dominator starts the game and the Staller-start game domination number ▫$gamma'_g(G)$▫ when Staller starts the game. It is proved that for any graph ▫$G$▫, ▫$gamma(G) le gamma_g(G) le 2gamma(G) - 1$▫, and that all possible values can be realized. It is also proved that for any graph ▫$G$▫, ▫$gamma_g(G) - 1 le gamma'_g(G) le gamma_g(G) + 2$▫, and that most of the possibilities for mutual values of ▫$gamma_g(G)$▫ and ▫$gamma'_g(G)$▫ can be realized. A connection with Vizing's conjecture is established and several problems and conjectures stated.
Ključne besede: teorija grafov, teorija iger, dominantnost, Vizingova domneva, graph theory, game theory, domination, domination game, game domination number, Vizing's conjecture
Objavljeno v DKUM: 10.07.2015; Ogledov: 1963; Prenosov: 31
Povezava na celotno besedilo |
5. Domination game played on trees and spanning subgraphsBoštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2011 Opis: Igra dominacije na grafu ▫$G$▫ je bila vpeljana v [B. Brešar, S. Klavžar, D. F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979-991]. Dva igralca, Dominator in Zavlačevalec, drug za drugim izbirata po eno vozlišče grafa. Vsako izbrano vozlišče mora povečati množico vozlišč, ki so bila dominirana do tega trenutka igre. Oba igralca izbirata optimalno strategijo, pri čemer Dominator želi igro končati v najmanjšem možnem številu korakov, Zavlačevalec pa v največjem možnem številu korakov. Igralno dominacijsko število ▫$gamma_g(G)$▫ je število izbranih vozlišč v igri, kjer je Dominator prvi izbral vozlišče. Ustrezno invarianto, ko igro začne Zavlačevalec, označimo z ▫$gamma_g'(G)$▫. V članku sta obe igri proučevani na drevesih in vpetih podgrafih. Dokazana je spodnja meja za igralno dominacijsko število drevesa, ki je funkcija njegovega reda in maksimalne stopnje. Pokazano je, da je meja asimptotično optimalna. Dokazano je, da za vsak ▫$k$▫ obstaja drevo ▫$T$▫ z ▫$(gamma_g(T),gamma_g'(T)) = (k,k+1)$▫ in postavljena je domneva, da ne obstaja drevo z ▫$(gamma_g(T),gamma_g'(T)) = (k,k-1)$▫. Obravnavana je povezava med igralnim dominacijskim številom grafa in njegovimi vpetimi podgrafi. Dokazano je, da za vsako naravno število ▫$ell geq 1$▫ obstaja graf ▫$G$▫ z vpetim drevesom ▫$T$▫, tako da velja ▫$gamma_g(G)-gamma_g(T)ge ell$▫. Nadalje obstajajo 3-povezani grafi ▫$G$▫, ki imajo vpeta drevesa z igralnim dominacijskim številom poljubno manjšim od ▫$G$▫.
Ključne besede: igra dominacije, igralno dominacijsko število, drevo, vpeti podgraf, graph theory, domination game, game domination number, tree, spanning subgraph
Objavljeno v DKUM: 10.07.2015; Ogledov: 1484; Prenosov: 92
Povezava na celotno besedilo |
