| | 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 - 10 / 41
Na začetekNa prejšnjo stran12345Na naslednjo stranNa konec
1.
A charaterization of planar median graphs
Iztok Peterin, 2006, izvirni znanstveni članek

Opis: Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs.
Ključne besede: mathematics, graf theory, median graphs, planar graphs, expansion
Objavljeno v DKUM: 31.03.2017; Ogledov: 550; Prenosov: 482
.pdf Celotno besedilo (137,39 KB)
Gradivo ima več datotek! Več...

2.
A note on Steiner intervals and betweenness
Manoj Changat, Anandavally K. Lakshmikuttyamma, Joseph Mathews, Iztok Peterin, Prasanth G. Narasimha-Shenoi, Aleksandra Tepeh, 2011, izvirni znanstveni članek

Opis: Geodetka in geodetski interval, ki je sestavljen iz vseh vozlišč, ki pripadajo kakšni geodetki med fiksnim parom vozlišč v povezanem grafu ▫$G$▫, sta sestavni del metrične teorije grafov. Prav tako je znano, da je Steinerjevo drevo (multi) množice s ▫$k$▫ (▫$k>2$▫) vozlišči, posplošitev geodetke. V (B. Brešar, M. Changat, J. Mathews, I. Peterin, P. G. Narasimha-Shenoi, A. Tepeh Horvat, Steiner intervals, geodesic intervals, and betweenness, Discrete Math. 309 (2009) 6114--6125) so se avtorji ukvarjali s ▫$k$▫-Steinerjevimi intervali ▫$S(u_{1},u_{2},ldots, u_{k})$▫ povezanih grafov (▫$k geq 3$▫) kot ▫$k$▫-arnimi posplošitvami geodetskih intervalov. Analogno sta bila iz binarne na ▫$k$▫-arno funkcijo posplošena tudi vmesnostni aksiom (b2) in monotoni aksiom(m) kot: za vsa vozlišča ▫$u_{1}, ldots, u_{k}, x, x_{1}, ldots, x_{k} in V(G)$▫, ki niso nujno različna ▫$$(b2)quad x in S(u_{1}, u_{2}, ldots, u_{k}) Rightarrow S(x, u_{2}, ldots, u_{k}) subseteq S(u_{1}, u_{2}, ldots, u_{k}),$$▫ ▫$$(m) quad x_{1}, ldots, x_{k} in S(u_{1}, ldots, u_{k})Rightarrow S(x_{1}, ldots,x_{k}) subseteq S(u_{1}, ldots, u_{k}).$$▫ Avtorji so v zgoraj omenjenem članku domnevali, da ▫$3$▫-Steinerjev interval povezanega grafa ▫$G$▫ zadošča vmesnostnemu aksiomu (b2) natanko tedaj, ko je vsak blok grafa ▫$G$▫ geodetski z diametrom največ 2. V tem delu dokažemo to domnevo. Pri tem dodatno dokažemo, da v vsakem geodetskem bloku z diametrom vsaj 3 obstaja izometrični cikel dolžine ▫$2k+1$▫, ▫$k>2$▫. Prav tako predstavimo dodaten aksiom (b2(2)), ki je smiseln le za 3-Steinerjeve intervale in pokažemo, da je le ta ekvivalenten monotonemu aksiomu.
Ključne besede: matematika, teorija grafov, Steinerjev interval, geodetski graf, vmesnost, mathematics, graph theory, Steiner interval, geodetic graph, betweenness
Objavljeno v DKUM: 10.07.2015; Ogledov: 677; Prenosov: 71
URL Povezava na celotno besedilo

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

Opis: 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.
Ključne besede: 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
Objavljeno v DKUM: 10.07.2015; Ogledov: 713; Prenosov: 88
URL Povezava na celotno besedilo

4.
Geodetic sets in graphs
Boštjan Brešar, Matjaž Kovše, Aleksandra Tepeh, 2011, samostojni znanstveni sestavek ali poglavje v monografski publikaciji

Opis: Na kratko so povzeti rezultati o geodetskih množicah v grafih. Po pregledu rezultatov iz prejšnjih raziskav se posvetimo geodetskemu številu in sorodnim invariantam v grafih. Podrobno so obravnavane geodetske množice kartezičnih produktov grafov in geodetske množice v medianskih grafih. Predstavljen je tudi algoritmični vidik in povezava z nekaterimi ostalimi koncepti iz teorije konveksnih in intervalskih struktur v grafih.
Ključne besede: matematika, teorija grafov, geodetsko število, geodetska množica, kartezični produkt, medianski graf, mejna množica, mathematics, graph theory, geodetic number, geodetic set, Cartesian product, median graph, boundary set
Objavljeno v DKUM: 10.07.2015; Ogledov: 514; Prenosov: 25
URL Povezava na celotno besedilo

5.
Cover-incomparability graphs and chordal graphs
Boštjan Brešar, Manoj Changat, Tanja Dravec, Joseph Mathews, Antony Mathews, 2010, izvirni znanstveni članek

Opis: Problem prepoznavanja grafov pokritij-neprimerljivosti (to je grafov, ki jih dobimo iz delno urejenih množic kot povezavno unijo njihovega grafa pokritij in grafa neprimerljivosti) je NP-poln v splošnem, kot so dokazali v [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], medtem ko je na primer očitno polinomski v razredu dreves. V tem članku se osredotočimo na razrede tetivnih grafov in dokažemo, da je vsak graf pokritij-neprimerljivosti, ki je tetiven graf, kar graf intervalov. Okarakteriziramo tiste delno urejene množice, ki imajo za graf pokritij-neprimerljivosti bločni graf, oziroma razcepljeni graf in tudi okarakteriziramo grafe pokritij-neprimerljivosti med bločnimi, oziroma razcepljenimi grafi. Slednji karakterizaciji dasta tudi linearen algoritem za prepoznavanje bločnih, oziroma razcepljenih grafov, ki so grafi pokritij-neprimerljivosti.
Ključne besede: matematika, teorija grafov, delno urejena množica, temeljni graf, tetiven graf, razcepljen graf, bločni graf, mathematics, graph theory, poset, underlying graph, chordal graph, split graf, block graph
Objavljeno v DKUM: 10.07.2015; Ogledov: 967; Prenosov: 79
URL Povezava na celotno besedilo

6.
The b-chromatic number of cubic graphs
Marko Jakovac, Sandi Klavžar, 2010, izvirni znanstveni članek

Opis: b-Kromatično število grafa ▫$G$▫ je največje celo število, za katero obstaja dobro ▫$k$▫-barvanje, v katerem vsak barvni razred vsebuje vsaj eno vozlišče, ki je sosednje z vsemi drugimi barvnimi razredi. Dokazano je, da je b-kromatično število kubičnih grafov enako 4 razen za Petersenov graf, ▫$K_{3,3}$▫, prizmo nad ▫$K_3$▫, in še en sporadičen primer na 10 vozliščih.
Ključne besede: teorija grafov, kromatično število, b-kromatično število, kubični graf, Petersenov graf, graph theory, chromatic number, b-chromatic number, cubic graph, Petersen graph
Objavljeno v DKUM: 10.07.2015; Ogledov: 623; Prenosov: 81
URL Povezava na celotno besedilo

7.
Infinite families of crossing-critical graphs with prescribed average degree and crossing number
Drago Bokal, 2010, izvirni znanstveni članek

Opis: Širan constructed infinite families of ▫$k$▫-crossing-critical graphs for every ▫$k ge 3$▫ and Kochol constructed such families of simple graphs for every ▫$k ge 2$▫. Richter and Thomassen argued that, for any given ▫$k ge 1$▫ and ▫$r ge 6$▫, there are only finitely many simple ▫$k$▫-crossing-critical graphs with minimum degree ▫$r$▫. Salazar observed that the same argument implies such a conclusion for simple ▫$k$▫-crossing-critical graphs of prescribed average degree ▫$r > 6$▫. He established existence of infinite families of simple ▫$k$▫-crossing-critical graphs with any prescribed rational average degree ▫$r in [4,6)$▫ for infinitely many ▫$k$▫ and asked about their existence for ▫$r in (3,4)$▫. The question was partially settled by Pinontoan and Richter, who answered it positively for ▫$r in (3frac{1}{2},4)$▫. The present contribution uses two new constructions of crossing critical simple graphs along with the one developed by Pinontoan and Richter to unify these results and to answer Salazar's question by the following statement: for every rational number ▫$r in (3,6)$▫ there exists an integer ▫$N_r$▫, such that, for any ▫$k > N_r$▫, there exists an infinite family of simple 3-connected crossing-critical graphs with average degree ▫$r$▫ and crossing number ▫$k$▫. Moreover, a universal lower bound on ▫$k$▫ applies for rational numbers in any closed interval ▫$I subset (3,6)$▫.
Ključne besede: matematika, teorija grafov, prekrižno število, kritičen graf, prekrižno-kritičen graf, povprečna stopnja, mathematics, graph theory, crossing number, critical graph, crossing-critical graph, average degree, graph
Objavljeno v DKUM: 10.07.2015; Ogledov: 868; Prenosov: 91
URL Povezava na celotno besedilo

8.
Steiner intervals, geodesic intervals, and betweenness
Boštjan Brešar, Manoj Changat, Joseph Mathews, Iztok Peterin, Prasanth G. Narasimha-Shenoi, Aleksandra Tepeh, 2009, izvirni znanstveni članek

Opis: Koncept ▫$k$▫-Steinerjevih intervalov naravno posplošuje geodetske (binarne) intervale. Definiran je kot preslikava ▫$S: Vtimes cdots times V longrightarrow 2^V$▫, kjer je ▫$S(u_1, dots ,u_k)$▫ množica tistih vozlišč grafa ▫$G$▫, ki ležijo na kakem Steinerjevem drevesu glede na multimnožico ▫$W = {u_1, dots ,u_k}$▫ vozlišč iz ▫$G$▫. V tem članku za vsako naravno število ▫$k$▫ dokažemo karakterizacijo razreda tistih grafov, v katerih imajo vsi ▫$k$▫-Steinerjevi intervali t.i. lastnost unije, ki pravi, da ▫$S(u_1,ldots, u_k)$▫ sovpada z unijo geodetskih intervalov ▫$I(u_i,u_j)$▫ med vsemi pari vozlišč iz ▫$W$▫. Izkaže se, da tedaj, ko je ▫$k>3$▫, ta razred sovpada z razredom grafov, v katerih ▫$k$▫-Steinerjev interval zadošča aksiomu monotonosti(m), kot tudi z razredom grafov, v katerih ▫$k$▫-Steinerjev interval zadošča aksiomu (b2), ki sta pogoja iz teorije vmesnosti. In sicer preslikava ▫$S$▫ zadošča aksiomu (m), če iz ▫$x_1, dots ,x_k in S(u_1, dots ,u_k)$▫ sledi ▫$S(x_1, dots ,x_k) subseteq S(u_1, dots ,u_k)$▫; ter ▫$S$▫ zadošča (b2), če iz ▫$x in S(u_1,u_2, dots ,u_k)$▫ sledi ▫$S(x,u_2, dots ,u_k) subseteq S(u_1, dots ,u_k)$▫. V primeru ▫$k=3$▫ so ti trije razredi grafov različni in za razreda grafov, v katerih Steinerjev interval zadošča lastnosti unije oz. aksiomu monotonosti (m), dokažemo strukturni karakterizaciji. Prav tako predstavimo več delnih ugotovitev za razred grafov, v katerih 3-Steinerjev interval zadošča aksimu (b2), ki vodijo do domneve, da so to natanko tisti grafi, v katerih je vsak blok geodetski graf z diametrom 2.
Ključne besede: matematika, teorija grafov, Steinerjev interval, geodetski interval, razdalja, vmesnost, monotonost, bločni graf, mathematics, graph theory, Steiner interval, geodesic interval, distance, betweenness, monotonicity, block graph
Objavljeno v DKUM: 10.07.2015; Ogledov: 674; Prenosov: 80
URL Povezava na celotno besedilo

9.
Lower bounds for domination and total domination number of direct products graphs
Gašper Mekiš, 2009

Opis: An exact lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: ▫$gamma(times_{i=1}^t K_{n_i} ge t+1$▫, ▫$t ge 3$▫. Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: ▫$gamma(G times H) ge gamma(G) + gamma(H) - 1$▫. Infinite families of graphs that attain the bound are presented. For these graphs it also holds ▫$gamma_t(G times H) = gamma(G) + gamma(H) - 1$▫. Some additional parallels with the total domination number are made.
Ključne besede: matematika, teorija grafov, dominacijska množica, dominacijsko število, celotna dominacijska množica, celotno dominacijsko število, direktni produkt grafov, poln graf, mathematics, graph theory, dominating set, domination number, total dominating set, total domination number, direct product graphs, complete graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 782; Prenosov: 32
URL Povezava na celotno besedilo

10.
Cube intersection concepts in median graphs
Boštjan Brešar, Tadeja Kraner Šumenjak, 2009, izvirni znanstveni članek

Opis: Obravnavamo različne razrede presečnih grafov maksimalnih hiperkock medianskih grafov. Za medianski graf ▫$G$▫ in celo število ▫$k ge 0$▫ je presečni graf ▫${mathcal{Q}}_k(G)$▫ definiran kot tisti graf, katerega vozlišča so maksimalne hiperkocke (z ozirom na inkluzijo) grafa ▫$G$▫ in sta dve vozlišči ▫$H_x$▫ in ▫$H_y$▫ v njem sosednji tedaj, ko presek ▫$H_x cap H_y$▫ vsebuje podgraf izomorfen ▫$Q_k$▫. V članku predstavimo karakterizacije kličnih grafov z uporabo omenjenih presečnih konceptov, ko je ▫$k>0$▫. Vpeljemo tudi t.i. maksimalno 2-presečni graf maksimalnih hiperkock medianskega grafa ▫$G$▫, ki ga označimo z ▫${mathcal{Q}}_{m2}(G)$▫ in predstavlja tisti graf, katerega vozlišča somaksimalne hiperkocke grafa ▫$G$▫, dve vozlišči v njem pa sta sosednji, če presek pripadajočih hiperkock ni strogo vsebovan v kakem preseku dveh maksimalnih hiperkock. Dokažemo, da je graf ▫$H$▫ brez induciranih diamantov, če in samo če obstaja takšen medianski graf ▫$G$▫, da je ▫$H$▫ izomorfen ▫${mathcal{Q}}_{m2}(G)$▫. Obravnavamo tudi konvergenco medianskega grafa h grafu na enem vozlišču glede na vse vpeljane operacije.
Ključne besede: matematika, teorija grafov, kartezični produkt, medianski graf, graf kock, presečni graf, konveksnost, mathematics, graph theory, Cartesian product, median graph, cube graph, intersection graph, convexity
Objavljeno v DKUM: 10.07.2015; Ogledov: 799; Prenosov: 93
URL Povezava na celotno besedilo

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