Domination game: extremal families of graphs for 3/5-conjectures

Boštjan Brešar (Avtor), Sandi Klavžar (Avtor), Gašper Košmrlj (Avtor), Douglas F. Rall (Avtor)

Povzetek

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;

Podatki

Jezik:	Angleški jezik
Leto izida:	2013
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.17:004
COBISS:	16614745
ISSN:	0166-218X
Št. ogledov:	395
Št. prenosov:	30
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Dominacijska igra: ekstremne družine grafov za 3/5-domneve
Sekundarni povzetek:	Two players, Dominator and Staller, alternate choosing vertices of a graph ▫$G$▫, one at a time, such that each chosen vertex enlarges the set of vertices dominated so far. The aim of the Dominator is to finish the game as soon as possible, while the aim of the Staller is just the opposite. The game domination number ▫$\gamma_g(G)$▫ is the number of vertices chosen when Dominator starts the game and both players play optimally. It has been conjectured [W.B. Kinnersley, D.B. West, R. Zemani, Extremal problems for game domination number, Manuscript, 2012] that ▫$\gamma_g(G) \le \frac{3\|V(G)\|}{5}$▫ holds for an arbitrary graph ▫$G$▫ with no isolated vertices, which is in particular open when ▫$G$▫ is a forest. In this paper we present constructions that lead to large families of trees that attain the conjectured ▫$3/5$▫-bound. Some of these families can be used to construct graphs with game domination number ▫$3/5$▫ of their order by gluing them to an arbitrary graph. All extremal trees on up to 20 vertices were found by computer. In particular, there are exactly ten trees ▫$T$▫ on 20 vertices with ▫$\gamma_g(T) = 12$▫ all of which belong to the constructed families.
Sekundarne ključne besede:	matematika;teorija grafov;dominacijska igra;igralno dominacijsko številko;3/5-domneva;računalniško iskanje;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1308-1316
Letnik:	Vol. 161
Zvezek:	iss. 10-11
Čas izdaje:	2013
ID:	1476815