| | 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 - 6 / 6
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
2.
Cover-incomparability graphs of posets
Boštjan Brešar, Manoj Changat, Sandi Klavžar, Matjaž Kovše, Joseph Mathews, Antony Mathews, 2008, izvirni znanstveni članek

Opis: Vpeljemo graf pokritij-neprimerljivosti (ki mu na kratko rečemo CI-graf), katerega množica povezav je unija množic povezav grafa neprimerljivosti in grafa pokritja dane delno urejene množice. S pomočjo prepovedanih izometričnih delno urejenih podmnožic, okarakteriziramo tiste delno urejene množice, katerih CI-graf je tetiven (razdaljno-hereditaren, ptolemajski) in predlagamo splošen pristop k obravnavi CI-grafov. Predstavimo tudi več odprtih problemov.
Ključne besede: matematika, teorija grafov, delno urejena množica, temeljni graf, tranzitna funkcija, tetiven graf, razdaljno-hereditaren graf, mathematics, graph theory, poset, underlying graph, transit function, chordal graph, distance-hereditary graph, claw
Objavljeno: 10.07.2015; Ogledov: 345; Prenosov: 61
URL Povezava na celotno besedilo

3.
Cage-amalgamation graphs, a common generalization of chordal and median graphs
Boštjan Brešar, Aleksandra Tepeh, 2009, izvirni znanstveni članek

Opis: 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$▫.
Ključne besede: matematika, teorija grafov, medianski grafi, tetivni grafi, konveksnost, amalgamacija, enakosti drevesnega tipa, mathematics, graph theory, median graphs, chordal graphs, convexity, amalgamation, tree-like equalities
Objavljeno: 10.07.2015; Ogledov: 265; Prenosov: 47
URL Povezava na celotno besedilo

4.
Cover-incomparability graphs and chordal graphs
Boštjan Brešar, Manoj Changat, Tanja Gologranc, 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: 10.07.2015; Ogledov: 479; Prenosov: 55
URL Povezava na celotno besedilo

5.
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: 10.07.2015; Ogledov: 346; Prenosov: 61
URL Povezava na celotno besedilo

6.
A forbidden subgraph characterization of some graph classes using betweenness axioms
Manoj Changat, Anandavally K. Lakshmikuttyamma, Joseph Mathews, Iztok Peterin, Prasanth G. Narasimha-Shenoi, Geetha Seethakuttyamma, Simon Špacapan, 2013, izvirni znanstveni članek

Opis: Naj bo ▫$I_G(x,y)$▫ interval najkrajših ▫$x,y$▫-poti in ▫$J_G(x,y)$▫ interval induciranih ▫$x,y$▫-poti v povezanem grafu ▫$G$▫. Obravnavani so naslednji trije aksiomi vmesnosti za množico ▫$V$▫ in ▫$R: V times V rightarrow 2^V$▫: (i) ▫$x in R(u,y), y in R(x,v), x neq y, |R(u,v)|>2 Rightarrow x in R(u,v)$▫; (ii) ▫$x in R(u,v) Rightarrow R(u,x) cap R(x,v) = {x}$▫; (iii) ▫$x in R(u,y), y in R(x,v), x neq y, Rightarrow x in R(u,v)$▫. Karakteriziramo razred grafov, za katere ▫$I_G$▫ izpolnjuje (i), razred grafov, za katere ▫$J_G$▫ izpolnjuje (ii) in razred grafov, kjer oba ▫$I_G$▫ in ▫$J_G$▫ izpolnjujeta (iii). Karakterizacije so podane z prepovedanimi induciranimi podgrafi. Izkaže se, da je razred grafov, kjer ▫$I_G$▫ izpolnjuje (i), pravi podrazred razdaljno dednih grafov in da je razred, kjer ▫$J_G$▫ izpolnjuje (ii), pravi nadrazred razdaljno dednih grafov. Podani sta tudi aksiomatični karakterizaciji tetivnih in ptolomejskih grafov.
Ključne besede: matematika, teorija grafov, prepovedani podgrafi, inducirana pot, intervalna funkcija, aksiomi vmesnosti, tetivni grafi, razdaljno dedni grafi, mathematics, graph theory, forbidden subgraphs, induced path, interval function, betweenness axioms, chordal graphs, distance hereditary graphs
Objavljeno: 10.07.2015; Ogledov: 414; Prenosov: 64
URL Povezava na celotno besedilo

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