| | 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 - 2 / 2
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
Guarded subgraphs and the domination game
Boštjan Brešar, Sandi Klavžar, Gašper Košmrlj, Douglas F. Rall, 2015, izvirni znanstveni članek

Opis: V članku vpeljemo koncept zaščitenega podgrafa. Množica le-teh po definicji leži med množico konveksnih in 2-izometričnih podgrafov, hkrati pa ni primerljiva z množico izometričnimih podgrafov. Dokažemo nekatere metrične lastnosti zaščitenih podgrafov ter koncept uporabimo v dominacijski igri, v kateri dva igralca, Dominator in Zavlačevalka, izmenično izbirata vozlišča grafa, tako da vsako izbrano vozlišče poveča množico dominiranih vozlišč. Dominatorjev cilj je končati igro, tj. dominirati celoten graf, čim hitreje, medtem ko je Zavlačevalkin cilj odigrati čim več potez. Igralno dominacijsko število je število potez v igri, ko Dominator začne in oba igralca igrata optimalno. Kot glavni rezultat članka dokažemo, da igralno dominacijsko število grafa ni nikoli manjše, kot igralno dominacijsko število njegovega zaščitenega podgrafa. Predstavljenih je tudi več aplikacij tega rezultata.
Ključne besede: dominacijska igra, igralno dominacijsko številko, konveksni podgraf, (2-)izometrični podgraf
Objavljeno: 10.07.2017; Ogledov: 710; Prenosov: 93
.pdf Celotno besedilo (690,85 KB)
Gradivo ima več datotek! Več...

2.
Domination game: extremal families of graphs for 3/5-conjectures
Boštjan Brešar, Sandi Klavžar, Gašper Košmrlj, Douglas F. Rall, 2013, izvirni znanstveni članek

Opis: 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
Objavljeno: 10.07.2015; Ogledov: 835; Prenosov: 75
URL Povezava na celotno besedilo

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