ALL libraries (COBIB.SI union bibliographic/catalogue database)
13.
The competition-independence game with prevention
Brešar, Boštjan ; Mesarič Štesl, Daša
Neodvisno dominacijsko igro, kot sta jo vpeljala Phillips in Slater, igrata na grafu dva igralca, Zmanjševalec in Napihovalec, ki si izmenjujeta poteze, v katerih lahko izbereta poljubno vozlišče, ki ...ni v zaprti soseščini kateregakoli od predhodno izbranih vozlišč. Cilj Zmanjševalca je ob koncu igre minimizirati (neodvisno) množico izbranih vozlišč, Napihovalčev cilj pa je ravno nasproten. Ob predpostavki, da oba igralca igrata optimalno glede na izbrana cilja, se porodita dve grafovski invarianti glede na to, kdo začne igro. V tem članku vpeljemo variacijo opisane igre, v kateri igralca lahko vsakič uporabita alternativno obliko poteze, pri kateri lahko označita (in ne izbereta!) poljubno vozlišče ▫$x$▫, ki še ni bilo odigrano, s čimer preprečita, da bi ▫$x$▫ bil izbran kadarkoli do konca igre. Med drugim to tudi pomeni, da ▫$x$▫ ne bo v končni množici izbranih vozlišč. Za dani graf ▫$G$▫ in ob predpostavki, da oba igralca igrata optimalno glede na svoja cilja, označimo s ▫$\widetilde{I}_{\rm d}(G)$▫ (oziroma ▫$\widetilde{I}_{\rm s}(G)$▫) moč množice izbranih vozlišč v neodvisni igri s preprečevanjem, ob pogoju da Zmanjševalec (oziroma Napihovalec) začne igro. Z uporabo Particijske strategije dokažemo, da za vsako naravno število ▫$n$▫ velja ▫$\widetilde{I}_{\rm d}(P_n)=\lfloor\frac{2n+3}{6}\rfloor$▫ in ▫$\widetilde{I}_{\rm s}(P_n)=\lfloor\frac{2n+4}{6}\rfloor$▫. Medtem ko ni težko ugotoviti splošnih mej, ▫$1\le \widetilde{I}_{\rm d}(G)\le \lfloor\frac{n}{2}\rfloor$▫ in ▫$1\le \widetilde{I}_{\rm s}(G)\le \lceil\frac{n}{2}\rceil$▫, v članku okarakteriziramo družine grafov, pri katerih v vsaki posamezni zgornji ali spodnji meji velja enakost. Nazadnje ugotovimo še tesno povezavo nove igre z variacijo igre barvanja, ki se imenuje pakirna igra barvanja, na grafih s premerom ▫$2$▫, zastavimo pa tudi več odprtih problemov.
It was not necessary to add the material to the shelf.
Bibliographic material was successfully added on shelf.
Adding bibliographical material on shelf was not successful.
Material is already on the shelf.
Permalink
URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year
Impact factor
Edition
Category
Classification
JCR
SNIP
JCR
SNIP
JCR
SNIP
JCR
SNIP
Select the library membership card:
DRS,
in which the journal is indexed
Database name
Field
Year
Links to authors' personal bibliographies
Links to information on researchers in the SICRIS system
Subject headings in COBISS General List of Subject Headings
Select pickup location
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
