| | 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


21 - 30 / 97
Na začetekNa prejšnjo stran12345678910Na naslednjo stranNa konec
21.
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

22.
The cube polynomial and its derivatives: the case of median graphs
Boštjan Brešar, Sandi Klavžar, Riste Škrekovski, 2003, izvirni znanstveni članek

Opis: Naj bo ▫$alpha_i(G)$▫ število induciranih ▫$i$▫-kock grafa ▫$G$▫. Tedaj je polinom kock ▫$c(G,x)$▫ grafa ▫$G$▫ definiran z ▫$sum_{i ge 0} alpha_i (G) x_i$▫. Pokazano je, da je vsaka funkcija ▫$f$▫ z dvemi predpisanimi naravnimi lastnostmi do faktorja ▫$f(Q_0,x)$▫ enaka polinomu kock. Vpeljan je tudi odvod ▫$partial G$▫ medianskega grafa ▫$G$▫. Dokazano je, da je polinom kock edina funkcija ▫$f$▫ z lastnostjo ▫$f'(G,z) = f(partial G,x)$▫, če je le ▫$f(G,0) = |V(G)|$▫. Dokazanih je tudi več relacij za medianske grafe, ki posplošujejo prej znane rezultate. Na primer, za vsak ▫$s ge 0$▫ velja ▫$c^{(s)}(G, x+1) = sum_{i ge s} frac{c^{(s)}(G,x)}{(i-s)!}$▫.
Ključne besede: matematika, teorija grafov, polinom kock, odvod grafa, medianski grafi, mathematics, graph theory, cube polynomials, graph derivation, median graphs
Objavljeno: 10.07.2015; Ogledov: 284; Prenosov: 9
URL Povezava na celotno besedilo

23.
Roots of cube polynomials of median graphs
Boštjan Brešar, Sandi Klavžar, Riste Škrekovski, 2006, izvirni znanstveni članek

Opis: Polinom kock ▫$c(G,x)$▫ grafa ▫$G$▫ je definiran z ▫$sum_{i ge 0}alpha_i(G)x^i$▫, kjer ▫$alpha_i(G)$▫ označuje število induciranih ▫$i$▫-kock v ▫$G$▫. Naj bo ▫$G$▫ medianski graf. Dokazano je, da je vsaka racionalna ničla polinoma ▫$c(G,x)$▫ oblike ▫$-frac{t+1}{t}$▫ za neko celo število ▫$t>0$▫ in da ima ▫$c(G,x)$▫ vedno realno ničlo na intervalu ▫$[-2,-1)$▫. Nadalje ima ▫$c(G,x)$▫ ▫$p$▫-kratno ničlo natanko tedaj, ko je ▫$G$▫ kartezični produkt ▫$p$▫ dreves istega reda. Grafi acikličnih kubičnih kompleksov so karakterizirani kot grafi za katere velja ▫$c(H,-2)=0$▫ za vsak 2-povezan konveksen podgraf ▫$H$▫.
Ključne besede: matematika, teorija grafov, polinom kock, koren, medianski graf, kartezični produkt grafov, mathematics, graph theory, cube polynomial, root, median graph, Cartesian product
Objavljeno: 10.07.2015; Ogledov: 411; Prenosov: 46
URL Povezava na celotno besedilo

24.
[Theta]-graceful labelings of partial cubes
Boštjan Brešar, Sandi Klavžar, 2006, izvirni znanstveni članek

Opis: Delne kocke so grafi, ki dopuščajo izometrične vložitve v hiperkocke. V članku so vpeljane ▫$Theta$▫-gracilne označitve delnih kock kot naravna razširitev gracilnih označitev dreves. Pokazano je, da so različni razredi delnih kock ▫$Theta$▫-gracilni, na primer sodi cikli, Fibonaccijeve kocke in (na novo vpeljane) leksikografske podkocke. Kartezični produkt ▫$Theta$▫-gracilnih delnih kock je spet tak in sprašujemo se, ali je morda vsaka delna kocka ▫$Theta$▫-gracilna. Pokazana je povezava med ▫$Theta$▫-gracilnimi označitvami in reprezentacijami celih števil v določenih številskih sistemih. Predlaganih je tudi nekaj smeri za nadaljnje raziskovanje.
Ključne besede: matematika, teorija grafov, drevesa, Ringel-Kotzigova domneva, delne kocke, Fibonaccijeve kocke, hiperkocke, mathematics, graph theory, graceful labelings, trees, Ringel-Kotzig conjecture, partial cubes, Fibonacci cubes, hypercubes
Objavljeno: 10.07.2015; Ogledov: 274; Prenosov: 17
URL Povezava na celotno besedilo

25.
On integer domination in graphs and Vizing-like problems
Boštjan Brešar, Michael A. Henning, Sandi Klavžar, 2006, izvirni znanstveni članek

Opis: Nadaljujemo študij ▫${k}$▫-dominantnih funkcij v grafih (ali, kot bomo tudi rekli, celoštevilske dominacije), ki so jo začeli Domke, Hedetniemi, Laskar in Fricke. Za celo število ▫$k ge 1$▫ je funkcija ▫$f: V(G) to {0,1,...,k}$▫, definirana na točkah grafa ▫$G$▫, ▫${k}$▫-dominantna funkcija, če je vsota funkcijskih vrednosti na vsaki zaprti okolici vsaj ▫$k$▫. Teža ▫${k}$▫-dominantne funkcije je vsota funkcijskih vrednosti po vseh točkah. ▫${k}$▫-dominantno število grafa ▫$G$▫ je najmanjša teža ▫${k}$▫-dominantne funkcije na ▫$G$▫. Obravnavamo ▫${k}$▫-dominantno število kartezičnega produkta grafov, predvsem probleme povezane s slavno Vizingovo domnevo. Študirana je tudi povezava med ▫${k}$▫-dominantnim številom in drugimi tipi dominacijskih parametrov.
Ključne besede: matematika, teorija grafov, ▫${k}$▫-dominantna funkcija, celoštevilska dominacija, Vizingova domneva, kartezični produkt grafov, mathematics, graph theory, ▫${k}$▫-dominating function, integer domination, Vizing's conjecture, Cartesian product
Objavljeno: 10.07.2015; Ogledov: 427; Prenosov: 31
URL Povezava na celotno besedilo

26.
On cube-free median graphs
Boštjan Brešar, Sandi Klavžar, Riste Škrekovski, 2007, izvirni znanstveni članek

Opis: Naj bo ▫$G$▫ mediansk graf brez 3-kocke. Pokazano je, da velja ▫$frac{k}{2} ge sqrt{n}-1 ge frac{m}{2sqrt{n}} ge sqrt{s} ge r-1$▫, kjer so ▫$n, m, s, k$▫ in ▫$r$▫ števila točk, povezav, kvadratov, ▫$Theta$▫-razredov in število povezav najmanšega ▫$Theta$▫-razreda grafa ▫$G$▫. Enakosti so dosežene natanko tedaj, ko je ▫$G$▫ kartezični produkt dveh dreves istega reda. Obravnavan je tudi polinom kock medianskih grafov in pokazano je, da lahko ravninske medianske grafe brez 3-kocke prepoznamo v linearnem času.
Ključne besede: matematika, teorija grafov, medianski graf, kartezični produkt, prepoznavni algoritem, mathematics, graph theory, median graph, cube-free graph, Cartesian product, recognition algoritem
Objavljeno: 10.07.2015; Ogledov: 369; Prenosov: 11
URL Povezava na celotno besedilo

27.
Nonrepetitive colorings of trees
Boštjan Brešar, J. Grytczuk, Sandi Klavžar, S. Niwczyk, Iztok Peterin, 2007, izvirni znanstveni članek

Opis: Barvanje vozlišč grafa ▫$G$▫ je neponavljajoče, če nobena pot v ▫$G$▫ ne tvori zaporedja sestavljenega iz dveh identičnih blokov. Najmanjše število barv, ki jih potrebujemo za tako barvanje, je Thuejevo kromatično število, označimo ga s ▫$pi(G)$▫. Slavni Thuejev izrek trdi, da je ▫$pi(P) = 3$▫ za vsako pot ▫$P$▫ z vsaj štirimi vozlišči. V članku študiramo Thuejevo kromatično število na drevesih. Glede na to,da je v tem razredu ▫$pi(T)$▫ omejeno s 4, je naš namen opisati 4-kromatična drevesa. V posebnem obravnavamo 4-kritična drevesa, ki so minimalna glede na to lastnost. Čeprav obstaja mnogo dreves ▫$T$▫ s ▫$pi(T) = 4$▫, pokažemo, da ima vsako od njih primerno veliko subdivizijo ▫$H$▫, tako da je ▫$pi(H)=3$▫. Dokaz se opira na Thuejeva zaporedja z dodatnimi lastnostmi, ki vključujejo palindromske besede. Obravnavamo tudi neponavljajoča barvanja povezav na drevesih. S podobnimi argumenti dokažemo, da ima vsako drevo subdivizijo, ki jo lahko po povezavah pobarvamo z največ ▫$Delta +1$▫ barvami brez ponavljanja na poteh.
Ključne besede: kombinatorika na besedah, neponavljajoče zaporedje, Thuejevo kromatično število, drevo, palindrom, combinatorics on words, nonrepetitive sequence, Thue chromatic number, tree, palindrome
Objavljeno: 10.07.2015; Ogledov: 435; Prenosov: 50
URL Povezava na celotno besedilo

28.
Characterizing almost-median graphs
Boštjan Brešar, 2007, izvirni znanstveni članek

Opis: Skoraj medianski grafi in semi-medianski grafi sta dve naravni posplošitvi dobro znanega razreda medianskih grafov. V članku dokažemo, da je semi-medianski graf skoraj medianski, če in samo če ne vsebuje konveksnega cikla dolžine večje kot štiri.
Ključne besede: matematika, teorija grafov, medianski graf, konveksen cikel, delna kocka, mathematics, graf theory, median graph, convex cycle, partial cube
Objavljeno: 10.07.2015; Ogledov: 360; Prenosov: 56
URL Povezava na celotno besedilo

29.
Maximal proper subgraphs of median graphs
Boštjan Brešar, Sandi Klavžar, 2007, izvirni znanstveni članek

Opis: Za medianski graf ▫$G$▫ in vozlišče ▫$v$▫, ki ni presečno, dokažemo, da je ▫$G-v$▫ medianski graf natanko tedaj, ko ▫$v$▫ ni center dvodelnega kolesa. To je nadalje ekvivalentno obstoju določene eliminacijske sheme za povezave, ki so incidenčne z ▫$v$▫. Rezultat implicira karakterizacijo po vozliščih kritičnih (po vozliščih polnih) medianskih grafov, ki so medianski grafi, katerih vsi podgrafi brez enega vozlišča niso medianski (so medianski). Podani sta tudi dve analogni karakterizaciji za primer odstranjevanja povezav.
Ključne besede: matematika, teorija grafov, medianski graf, podgraf brez enega vozlišča, dvodelno kolo, kvadratna povezava, mathematics, graph theory, median graph, vertex-deleted subgraph, bipartite wheel, square-eddge, square-dismantlable vertex
Objavljeno: 10.07.2015; Ogledov: 290; Prenosov: 43
URL Povezava na celotno besedilo

30.
Dominating direct products of graphs
Boštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2007, izvirni znanstveni članek

Opis: Dokazana je zgornja meja za dominantno število direktnega produkta grafov. V posebnem primeru iz meje sledi, da za poljubna grafa ▫$G$▫ in ▫$H$▫ velja ▫$gamma (G times H) le 3gamma(G)gamma(H)$▫. Konstruirani so grafi s poljubno velikimi dominantnimi števili, za katere je ta meja dosežena. Za gornje dominantno število dokažemo, da velja ▫$Gamma(G times H) ge Gamma(G)Gamma(H)$▫, s čimer je potrjena domneva iz [R. Nowakowski, D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79]. Nazadnje za dominacijo v parih direktnih produktov dokažemo, da za poljubna grafa ▫$G$▫ in ▫$H$▫ velja ▫$gamma_{rm{pr}}(G times H) le gamma_{rm{pr}} (G)gamma_{rm{pr}}(H)$▫. Predstavimo tudi neskončne družine grafov, pri katerih je ta meja dosežena.
Ključne besede: matematika, teorija grafov, dominacija, dominacija v parih, gornja dominacija, kartezični produkt grafov, mathematics, graph theory, domination, paired-domination, upper domination, direct product
Objavljeno: 10.07.2015; Ogledov: 334; Prenosov: 50
URL Povezava na celotno besedilo

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