| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


41 - 50 / 58
First pagePrevious page123456Next pageLast page
41.
Characterizing subgraphs of Hamming graphs
Sandi Klavžar, Iztok Peterin, 2005, original scientific article

Abstract: Kartezični produkti polnih grafov so znani kot Hammingovi grafi. Z uporabo vložitev v kartezične produkte kvocientnih grafov so karakterizirani podgrafi, inducirani podgrafi in izometrični podgrafi Hammingovih grafov. Na primer, graf ▫$G$▫ je inducirani podgraf Hammingovega grafa natanko tedaj, ko obstaja označitev povezav grafa ▫$G$▫, ki zadošča naslednjima pogojema: (i) povezave trikotnika imajo isto oznako, (ii) za vsaki točki ▫$u$▫ in ▫$v$▫ na razdalji vsaj 2 obstajata dve taki oznaki, ki se pojavita na vsaki inducirani poti med ▫$u$▫ in ▫$v$▫.
Keywords: matematika, teorija grafov, Hammingovi grafi, inducirani podgrafi, izometrični podgrafi, kartezični produkt grafov, označevanje povezav, kvocientni grafi, mathematics, graph theory, Hamming graphs, induced subgraphs, isometric subgraphs, edge-labelings, Cartesian products, quotient graphs
Published: 10.07.2015; Views: 560; Downloads: 61
URL Link to full text

42.
Wide and fault diameters of Cartesian graph bundles
Janez Žerovnik, Iztok Banič, Rija Erveš, 2008, published scientific conference contribution abstract

Keywords: matematika, teorija grafov, kartezični produkt grafov
Published: 10.07.2015; Views: 346; Downloads: 12
URL Link to full text

43.
The distinguishing chromatic number of Cartesian products of two complete graphs
Janja Jerebic, Sandi Klavžar, 2008

Abstract: Označitev grafa ▫$G$▫ je razlikovalna, če jo ohranja le trivialni avtomorfizem grafa ▫$G$▫. Razlikovalno kromatično število grafa ▫$G$▫ je najmanjše naravno število, za katero obstaja razlikovalna označitev grafa, ki je hkrati tudi dobro barvanje. Za vse ▫$k$▫ in ▫$n$▫ je določeno razlikovalno kromatično število kartezičnih produktov ▫$K_kBox K_n$▫. V večini primerov je enako kromatičnemu številu, kar med drugim odgovori na vprašanje Choia, Hartkeja and Kaula, ali obstajajo še kakšni drugi grafi, za katere velja enakost.
Keywords: teorija grafov, razlikovalno kromatično število, grafovski avtomorfizem, kartezični produkt grafov, graph theory, distinguishing chromatic number, graph automorphism, Cartesian product of graphs
Published: 10.07.2015; Views: 611; Downloads: 65
URL Link to full text

44.
On domination numbers of graph bundles
Blaž Zmazek, Janez Žerovnik, 2005

Abstract: Let ▫$gamma(G)$▫ be the domination number of a graph ▫$G$▫. It is shown that for any ▫$k ge 0$▫ there exists a Cartesian graph bundle ▫$B Box_varphi F$▫ such that ▫$gamma(B Box_varphi F) = gamma(B)gamma(F) - 2k$▫. The domination numbers of Cartesian bundles of two cycles are determined exactly when the fibre graph is a triangle or a square. A statement similar to Vizing's conjecture on strong graph bundles is shown not to be true by proving the inequality ▫$gamma(B boxtimes_varphi F) le gamma(B)gamma(F)$▫ for strong graph bundles. Examples of graphs ▫$B$▫ and ▫$F$▫ with ▫$gamma(B boxtimes_varphi F) < gamma(B)gamma(F)$▫ are given.
Keywords: matematika, teorija grafov, kartezični produkt grafov, dominantno število, dominantna množica, grafovski sveženj, mathematics, graph theory, graph bundle, dominating set, domination number, Cartesian product
Published: 10.07.2015; Views: 794; Downloads: 77
URL Link to full text

45.
Roots of cube polynomials of median graphs
Boštjan Brešar, Sandi Klavžar, Riste Škrekovski, 2003

Abstract: 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$▫.
Keywords: matematika, teorija grafov, polinom kock, koren, medianski graf, kartezični produkt grafov, mathematics, graph theory, cube polynomial, root, median graph, Cartesian product
Published: 10.07.2015; Views: 592; Downloads: 69
URL Link to full text

46.
On cube-free median graphs
Boštjan Brešar, Sandi Klavžar, Riste Škrekovski, 2003

Abstract: 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.
Keywords: matematika, teorija grafov, medianski graf, kartezični produkt, prepoznavni algoritem, mathematics, graph theory, median graph, cube-free graph, Cartesian product, recognition algoritem
Published: 10.07.2015; Views: 746; Downloads: 20
URL Link to full text

47.
On subgraphs of Cartesian product graphs
Sandi Klavžar, Alenka Lipovec, Marko Petkovšek, 1999

Abstract: Karakterizirani so grafi, ki jih lahko predstavimo kot netrivialen podgraf kartezičnega produkta grafov. Kot posledica je pokazano, da ima vsak dvodelni graf z radijem 2, ki ne vsebuje ▫$K_{2,3}$▫, tako predstavitev. Neskončna družina bazičnih podgrafov je tudi konstruirana - dosedaj je bilo znanih le končno takih grafov.
Keywords: matematika, teorija grafov, kartezični produkt grafov, podgrafi, mathematics, graph theory, Cartesian product graphs, subgraphs
Published: 10.07.2015; Views: 581; Downloads: 61
URL Link to full text

48.
Primeri uporabe mostovnih grafov in njihovih posplošitev
Tanja Gologranc, 2013, doctoral dissertation

Abstract: Mostovni grafi so zelo dobro raziskana družina grafov. Pojavljajo se na različnih področjih, ne samo diskretne matematike, na primer v geometrični teoriji grup. V disertaciji se ukvarjamo z različnimi problemi, povezanimi z mostovnimi grafi in njihovimi posplošitvami. Pokažemo, do so ti grafi uporabni tudi zunaj same teorije grafov, saj jih povežemo s teorijo kompleksov. Med drugim se ukvarjamo s povezavo teh grafov in določenih tipov konveksnosti v grafih in z uporabo mostovnih grafov v grafih, prirejenih delno urejenim množicam. Disertacija je sestavljena iz treh delov, pri čemer v vsakem delu prikažemo uporabnost mostovnih grafov na izbranem področju. V prvem delu vpeljemo in proučujemo bukolične komplekse, skupno posplošitev sistoličnih in CAT(0) kubičnih kompleksov. Bukolične komplekse proučujemo z vidika teorije grafov, topološkega vidika in iz perspektive geometrijske teorije grup. Okarakteriziramo jih preko določenih lastnosti njihovih 2-skeletov in 1-skeletov (ki jim pravimo bukolični grafi), s čimer posplošimo več že znanih rezultatov. Prav tako dokažemo, da so bukolični kompleksi skrčljivi in da zadoščajo nekim lastnostim tipa nepozitivnih ukrivljenosti. V drugem delu posplošene mostovne grafe obravnavamo vzporedno s 3-Steinerjevo konveksnostjo. In sicer dokažemo, da so grafi $G$, v katerih so j-krogle g_3-konveksne za vsak j ≥ 1, natanko grafi, ki ne vsebujejo hiše niti grafov K_{2,3} in W_4^- kot induciranih podgrafov, in je vsak cikel v G, dolžine vsaj šest, dobro premostljiv. Okarakteriziramo torej grafe z g_3-konveksnimi kroglami. V tretjem delu disertacije usmerimo pozornost na grafe pokritij-neprimerljivosti delno urejenih množic (C-I grafe) in iščemo njihovo povezavo z mostovnimi grafi. Pokažemo, da v razredu C-I grafov sovpada kar nekaj različnih grafovskih družin. In sicer, v razredu C-I grafov ni razlike med mostovnimi grafi, tetivnimi grafi in grafi intervalov. Ker je problem prepoznavanja grafov pokritij-neprimerljivosti v splošnem NP-poln, se osredotočimo na določene razrede mostovnih grafov. Okarakteriziramo tiste delno urejene množice, ki imajo za graf pokritij-neprimerljivosti bločni graf oziroma razcepljeni graf. Med drugim okarakteriziramo grafe pokritij-neprimerljivosti tako med bločnimi oziroma razcepljenimi grafi kot med tetivnimi kografi. Slednje karakterizacije dajo tudi linearen algoritem za prepoznavanje bločnih oziroma razcepljenih grafov, oziroma tetivnih kografov, ki so grafi pokritij-neprimerljivosti.
Keywords: kartezični produkt, delno urejena množica, retrakt, amalgamacija, mostovni graf, Steinerjev interval, šibko modularen graf, graf pokritij-neprimerljivosti
Published: 22.04.2015; Views: 1017; Downloads: 142
.pdf Full text (683,78 KB)

49.
Vozliščno pokritje k-poti v grafih
Igor Jesih, 2013, undergraduate thesis

Abstract: Diplomsko delo obravnava vozliščno pokritje k-poti v grafih. Na začetku so predstavljeni osnovni pojmi teorije grafov, ki so potrebni za razumevanje nadaljne snovi. V nalogo so vključeni pojmi NP-polnost, regularni grafi in drevesa. Konec pa vključuje vozliščna pokritja k-poti za nekatere grafovske produkte. Za velikost najmanjšega vozliščnega pokritja glede na stopnjo vozlišča bodo določene zgornje in spodnje meje grafa. Izboljšani bosta zgornja in spodnja ocena za najmanjše možno število vozlišč v pokritju k-poti pri kartezičnem, krepkem in leksikografskem produktu.
Keywords: Vozliščno pokritje, NP-polnost, regularni graf, kartezični produkt, krepki produkt, leksikografski produkt.
Published: 22.04.2013; Views: 1436; Downloads: 152
.pdf Full text (287,73 KB)

50.
DINAMIČNO BARVANJE GRAFOV
Tjaša Grahornik, 2012, undergraduate thesis

Abstract: V diplomskem delu je predstavljeno dinamično barvanje grafov. V uvodnih poglavjih so predstavljeni osnovni pojmi iz teorije grafov, ki so pomembni za razumevanje diplomskega dela. Pogledali si bomo kakšno je dinamično kromatično število za polne grafe, drevesa in cikle. V nalogi so opisane znane zgornje meje za dinamično kromatično število. Primerjali smo kromatično število in dinamično kromatično število za normalne grafe in regularne grafe. Ugotovili smo, da je razlika med dinamičnim kromatičnim številom in kromatičnim številom poljubno velika za nekatere grafe. Del diplomske naloge bomo posvetili tudi dinamičnemu barvanju kartezičnega produkta dveh grafov ter zaključili s posplošitvijo dinamičnega barvanja.
Keywords: dinamično barvanje grafov, zgornje meje, kartezični produkt, posplošitev dinamičnega barvanja
Published: 11.10.2012; Views: 1243; Downloads: 127
.pdf Full text (586,39 KB)

Search done in 0.31 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica