Domination game played on trees and spanning subgraphs

Brešar, Boštjan; Klavžar, Sandi; Rall, Douglas F.

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	Domination game played on trees and spanning subgraphs
Avtorji:	ID Brešar, Boštjan (Avtor) ID Klavžar, Sandi (Avtor) ID Rall, Douglas F. (Avtor)
Datoteke:	http://www.imfm.si/preprinti/PDF/01162.pdf
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
Organizacija:	FNM - Fakulteta za naravoslovje in matematiko
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
Leto izida:	2011
Št. strani:	str. 1-14
Številčenje:	Vol. 49, št. 1162
PID:	20.500.12556/DKUM-49395
ISSN:	2232-2094
UDK:	519.17:519.83
COBISS.SI-ID:	16027993
NUK URN:	URN:SI:UM:DK:7PFXGIJT
Datum objave v DKUM:	10.07.2015
Število ogledov:	1733
Število prenosov:	128
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.

Sekundarni jezik

Jezik:	Angleški jezik
Naslov:	Igra dominacije na drevesih in vpetih podgrafih
Opis:	The domination game, played on a graph ▫$G$▫, was introduced in [B. Brešar, S. Klavžar, D. F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979--991]. Vertices are chosen, one at a time, by two players Dominator and Staller. Each chosen vertex must enlarge the set of vertices of ▫$G$▫ dominated to that point in the game. Both players use an optimal strategy-Dominator plays so as to end the game as quickly as possible, Staller plays in such a way that the game lasts as many steps 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. In this paper these two games are studied when played on trees and spanning subgraphs. A lower bound for the game domination number of a tree in terms of the order and maximum degree is proved and shown to be asymptotically tight. It is shown that for every ▫$k$▫, there is a tree ▫$T$▫ with ▫$(gamma_g(T),gamma_g'(T)) = (k,k+1)$▫ and conjectured that there is none with ▫$(gamma_g(T),gamma_g'(T)) = (k,k-1)$▫. A relation between the game domination number of a graph and its spanning subgraphs is considered. It is proved that for any integer ▫$ell geq 1$▫, there exists a graph ▫$G$▫ and its spanning tree ▫$T$▫ such that ▫$gamma_g(G)-gamma_g(T)ge ell$▫. Moreover, there exist 3-connected graphs ▫$G$▫ having a spanning subgraph such that the game domination number of the spanning subgraph is arbitrarily smaller than that of ▫$G$▫.

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj