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


71 - 80 / 97
Na začetekNa prejšnjo stran12345678910Na naslednjo stranNa konec
71.
72.
73.
74.
75.
76.
On a local 3-Steiner convexity
Boštjan Brešar, Tanja Gologranc, 2011, izvirni znanstveni članek

Opis: Za dani graf ▫$G$▫ je Steinerjev interval množice vozlišč ▫$W subset V(G)$▫ množica tistih vozlišč, ki ležijo na kakem Steinerjevem drevesu glede na ▫$W$▫. Množica ▫$U subset V(G)$▫ je ▫$g_3$▫-konveksna v ▫$G$▫, če Steinerjev interval poljubne trojice vozlišč iz ▫$U$▫ v celoti leži v ▫$U$▫. Henning, Nielsen in Oellermann (2009) so dokazali, da graf ▫$G$▫, v katerem so ▫$j$▫-krogle ▫$g_3$▫-konveksne za vsak ▫$j ge 1$▫, ne vsebuje hiše niti grafov dvojčkov ▫$C_4$▫ kot induciranih podgrafov in vsak cikel v ▫$G$▫ dolžine vsaj šest je dobro premostljiv. V tem članku dokažemo, da velja tudi obrat tega izreka, s čimer okarakteriziramo grafe z ▫$g_3$▫-konveksnimi kroglami.
Ključne besede: matematika, teorija grafov, Steinerjev interval, razdalja, dobra premostljivost, mathematics, graph theory, Steiner interval, distance, well-bridgeness
Objavljeno: 10.07.2015; Ogledov: 285; Prenosov: 19
URL Povezava na celotno besedilo

77.
Vizing's conjecture: a survey and recent results
Boštjan Brešar, Paul Dorbec, Wayne Goddard, Bert L. Hartnell, Michael A. Henning, Sandi Klavžar, Douglas F. Rall, 2012, pregledni znanstveni članek

Opis: Vizingova domneva iz leta 1968 trdi, da je dominacijsko število kartezičnega produkta dveh grafov vsaj tako veliko, kot je produkt dominacijskih števil faktorjev. V članku naredimo pregled različnih pristopov k tej osrednji domnevi iz teorije grafovske dominacije. Ob tem dokažemo tudi nekaj novih rezultatov. Tako so na primer pokazane nove lastnosti minimalnega protiprimera, dokazana je tudi nova spodnja meja za produkte grafov brez induciranega ▫$K_{1,3}$▫ s poljubnimi grafi. Skozi celoten članek so obravnavani pripadajoči odprti problemi, vprašanja in sorodne domneve.
Ključne besede: matematika, teorija grafov, kartezični produkt, dominacija, Vizingova domneva, mathematics, graph theory, Caretesian product, domination, Vizing's conjecture
Objavljeno: 10.07.2015; Ogledov: 483; Prenosov: 39
URL Povezava na celotno besedilo

78.
A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks
Drago Bokal, Boštjan Brešar, Janja Jerebic, 2012, izvirni znanstveni članek

Opis: In this paper, we consider various problems concerning quasi-matchings and semi-matchings in bipartite graphs, which generalize the classical problem of determining a perfect matching in bipartite graphs. We prove a generalization of Hall's marriage theorem, and present an algorithm that solves the problem of determining a lexicographically minimum ▫$g$▫-quasi-matching (that is a set ▫$F$▫ of edges in a bipartite graph such that in one set of the bipartition every vertex ▫$v$▫ has at least ▫$g(v)$▫ incident edges from ▫$F$▫, where ▫$g$▫ is a so-called need mapping, while on the other side of the bipartition the distribution of degrees with respect to ▫$F$▫ is lexicographically minimum). We obtain that finding a lexicographically minimum quasi-matching is equivalent to minimizing any strictly convex function on the degrees of the A-side of a quasi-matching and use this fact to prove a more general statement: the optima of any component-based strictly convex cost function on any subset of ▫$L_1$▫-sphere in ▫${mathbb N}^n$▫ are precisely the lexicographically minimal elements of this subset. We also present an application in designing optimal CDMA-based wireless sensor networks.
Ključne besede: matematika, teorija grafov, prirejanje, kvazi prirejanje, polprirejanje, tok, madžarska metoda, mathematics, graph theory, matching, quasi-matching, semi-matching, flow, Hungarian method, augmenting path
Objavljeno: 10.07.2015; Ogledov: 371; Prenosov: 46
URL Povezava na celotno besedilo

79.
Bucolic complexes
Boštjan Brešar, Jérémie Chalopin, Victor Chepoi, Tanja Gologranc, Damian Osajda, 2012, izvirni znanstveni članek

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

80.
Domination game played on trees and spanning subgraphs
Boštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2013, izvirni znanstveni članek

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 obstajajo 3-povezani grafi ▫$G$▫, ki vsebujejo 2-povezani vpeti podgraf ▫$H$▫, tako da je igralno dominacijsko število grafa ▫$H$▫ poljubno manjše od igralnega dominacijskega števila grafa ▫$G$▫. Podobno je dokazano, da za vsako celo število ▫$ell ge 1$▫ obstajata graf ▫$G$▫ in njegov vpeti podgraf $T$, tako da velja ▫$gamma_g(G)-gamma_g(T) ge ell$▫. Po drugi strani obstajajo grafi ▫$G$▫, za katere je igralno dominacijsko število vsakega vpetega drevesa v ▫$G$▫ poljubno večje od igralnega dominacijskega števila 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: 469; Prenosov: 52
URL Povezava na celotno besedilo

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