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


1 - 5 / 5
First pagePrevious page1Next pageLast page
1.
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: 808; Downloads: 114
.pdf Full text (683,78 KB)

2.
Cage-amalgamation graphs, a common generalization of chordal and median graphs
Boštjan Brešar, Aleksandra Tepeh, 2009, original scientific article

Abstract: V članku je vpeljan in na različne načine okarakteriziran nov razred grafov, imenovan grafi amalgamov kletk, ki je vsebovan v šibko modularnih grafih in grafih zastraženih inverzov in ki vsebuje tako medianske kot tetivne grafe. Vpeljemo tudi variacijo Hammingovega polinoma in jo uporabimo pri izpeljavi dveh enakosti drevesnega tipa za ta razred grafov, ki sta bili prej znani za tetivne in medianske grafe. Prva enakost je ▫$sum_{ige 0}, (-1)^{i}, rho_i(G)=1$▫, kjer je ▫$rho_i(G)$▫ število ▫$i$▫-regularnih Hammingovih podgrafov v grafu amalgamov kletk ▫$G$▫.
Keywords: matematika, teorija grafov, medianski grafi, tetivni grafi, konveksnost, amalgamacija, enakosti drevesnega tipa, mathematics, graph theory, median graphs, chordal graphs, convexity, amalgamation, tree-like equalities
Published: 10.07.2015; Views: 279; Downloads: 51
URL Link to full text

3.
Retracts of products of chordal graphs
Boštjan Brešar, Jérémie Chalopin, Victor Chepoi, Matjaž Kovše, Arnaud Labourel, Yann Vaxès, 2010

Abstract: We characterize the graphs ▫$G$▫ that are retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs that do not contain ▫$K_{2;3}$▫, ▫$k$▫-wheels ▫$W_k$▫, and ▫$k$▫-wheels minus one spoke T$W_k^- ; (k ge 4)$T as induced subgraphs. We also show that these graphs ▫$G$▫ are exactly the cage-amalgamation graphs introduced by Brešar and Tepeh Horvat (2009); this solves the open question raised by these authors. Finally, we prove that replacing all products of cliques of $G$ by products of "solid" simplices, we obtain a polyhedral cell complex which, endowed with an intrinsic Euclidean metric, is a CAT(0) space. This generalizes similar results about median graphs as retracts of hypercubes (products of edges) and median graphs as 1-skeletons of CAT(0) cubical complexes.
Keywords: teorija grafov, graf, retrakt, zastražena amalgamacija, tetiven graf, kartezični produkt grafov, medianski graf, graph theory, graph, retract, gated amalgamation, chordal graph, Cartesian product of graphs, median graph
Published: 10.07.2015; Views: 368; Downloads: 66
URL Link to full text

4.
Bucolic complexes
Boštjan Brešar, Jérémie Chalopin, Victor Chepoi, Tanja Gologranc, Damian Osajda, 2012, original scientific article

Abstract: In this article, we introduce and investigate bucolic complexes, a common generalization of systolic complexes and of CAT(0) cubical complexes. This class of complexes is closed under Cartesian products and amalgamations over some convex subcomplexes. We study various approaches to bucolic complexes: from graph-theoretic and topological viewpoints, as well as from the point of view of geometric group theory. Bucolic complexes can be defined as locally-finite simply connected prism complexes satisfying some local combinatorial conditions. We show that bucolic complexes are contractible, and satisfy some nonpositive-curvature-like properties. In particular, we prove a version of the Cartan-Hadamard theorem, the fixed point theorem for finite group actions, and establish some results on groups acting geometrically on such complexes. We also characterize the 1-skeletons (which we call bucolic graphs) and the 2-skeletons of bucolic complexes. In particular, we prove that bucolic graphs are precisely retracts of Cartesian products of locally finite weakly bridged graphs (i.e., of 1-skeletons of weakly systolic complexes). We show that bucolic graphs are exactly the weakly modular graphs satisfying some local conditions formulated in terms of forbidden induced subgraphs and that finite bucolic graphs can be obtained by gated amalgamations of products of weakly bridged graphs.
Keywords: CAT(0) kubni in sistolični kompleksi, medianski in mostovni grafi, zastražena amalgamacija, kartezični produkt, prizmični kompleksi, retrakti, fiksne točke, asferičnost, CAT(0) cubical and systolic complexes, median and bridged graphs, gated amalgamation, Cartesian product, prism complexes, retracts, fixed points, asphericity
Published: 10.07.2015; Views: 399; Downloads: 9
URL Link to full text

5.
Bucolic complexes
Boštjan Brešar, Jérémie Chalopin, Victor Chepoi, Tanja Gologranc, Damian Osajda, 2013, original scientific article

Abstract: Vpeljemo in obravnavamo bukolične kompleksne, skupno posplošitev sistoličnih in CAT(0) kubnih kompleksov. Definirani so kot enostavno povezani kompleksi prizem, ki zadoščajo določenim lokalnim kombinatornim pogojem. Raziskujemo različne pristope k bukoličnim kompleksom: gledamo jih iz vidika teorije grafov in topološkega vidika kot tudi iz perspektive geometrijske teorije grup. Tako med drugim okarakteriziramo bukolične komplekse preko nekih lastnosti njihovih 2-skeletov in 1-skeletov (ki jim pravimo bukolični grafi), s čimer posplošimo več prej znanih rezultatov. Prav tako dokažemo, da so lokalno končni bukolični kompleksi kontraktibilni in da zadoščajo nekim lastnostim tipa nepozitivnih ukrivljenosti.
Keywords: CAT(0) kubni in sistolični kompleksi, medianski in mostovni grafi, zastražena amalgamacija, kartezični produkt, kompleksi prizem, retrakti, fiksne točke, asferičnost, CAT(0) cubical and systolic complexes, median and bridged graphs, gated amalgamation, Cartesian product, prism complexes, retracts, fixed points, asphericity
Published: 10.07.2015; Views: 438; Downloads: 12
URL Link to full text

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