The enclaveless competition game

angleški

2021

letnik 20, številka 1

dominacijska igra   tekmovalna brezenklavna igra

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Če je ?$S$? podmnožica vozlišč grafa ?$G$?, potem vozlišču ?$v \in S$? pravimo enklava množice ?$S$?, če je vozlišče ?$v$?, pa tudi vsi njegovi sosedje, v množici ?$S$?, pri čemer je sosed vozlišča v tisto vozlišče, ki je sosedno vozlišču ?$v$?. Množica ?$S$? je brezenklavna, če nima enklav. Brezenklavno število ?$\Psi(G)$? grafa ?$G$? je kardinalnost največje brezenklavne množice v ?$G$?. Kot je prvi opazil Slater leta 1997: če je ?$G$? graf na ?$n$? vozliščih, potem je ?$\gamma(G) + \Psi(G) = n$?, kjer je ?$\gamma(G)$? dobro raziskano dominacijsko število grafa ?$G$?. V članku nadaljujemo raziskavo tekmovalne brezenklavne igre, ki sta jo leta 2001 vpeljala Philips in Slater in je definirana takole: dva igralca izmenično konstruirata maksimalno brezenklavno množico ?$S$?, pri čemer en igralec, povečevalec, poizkuša maksimalizirati ?$|S|$?, drug igralec, pomanjševalec, pa poizkuša minimalizirati ?$|S|$?. Vrednost tekmovalne brezenklavne igre ?$\Psi_g^+(G)$? grafa ?$G$? je število vozlišč, dobljenih v primeru, da povečevalec začne igro in da oba igralca igrata optimalno. Poleg drugih problemov raziskujemo domnevo, da če je ?$G$? graf brez izoliranih vozlišč reda ?$n$?, potem je ?$\Psi_g^+(G) \geq \frac{1}{2} n$?. To domnevo dokažemo za regularne grafe in za brezkrempljaste grafe.

22.11.2022