| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 3 / 3
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
2.
Domination game played on trees and spanning subgraphs
Boš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: 10.07.2015; Ogledov: 604; Prenosov: 48
URL Povezava na celotno besedilo

3.
Domination game played on trees and spanning subgraphs
Boš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: 10.07.2015; Ogledov: 469; Prenosov: 52
URL Povezava na celotno besedilo

Iskanje izvedeno v 0.08 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici