| | 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 / 26
Na začetekNa prejšnjo stran123Na naslednjo stranNa konec
1.
Covering codes in Sierpiński graphs
Laurent Beaudou, Sylvain Gravier, Sandi Klavžar, Matjaž Kovše, Michel Mollard, 2010, izvirni znanstveni članek

Opis: Za dani graf ▫$G$▫ in celi števili ▫$a$▫ in ▫$b$▫ je ▫$(a,b)$▫-koda grafa ▫$G$▫ množica vozlišč ▫$C$▫, tako da ima vsako vozlišče iz ▫$C$▫ natanko ▫$a$▫ sosedov v ▫$C$▫, vsako drugo vozlišče pa natanko ▫$b$▫ sosedov v ▫$C$▫. V tem prispevku klasificiramo števila ▫$a$▫ in ▫$b$▫, za katera obstajajo ▫$(a,b)$▫-kode v grafih Sierpińskega.
Ključne besede: graph theory, codes in graphs, perfect codes, Sierpiński graphs
Objavljeno: 10.07.2017; Ogledov: 503; Prenosov: 88
.pdf Celotno besedilo (786,68 KB)
Gradivo ima več datotek! Več...

2.
On [Theta]-graphs of partial cubes
Sandi Klavžar, Matjaž Kovše, 2007, izvirni znanstveni članek

Opis: The ▫$\Theta$▫-graph ▫$\Theta(G)$▫ of a partial cube ▫$G$▫ is the intersection graph of the equivalence classes of the Djokovic-Winkler relation. ▫$\Theta$▫-graphs that are 2-connected, trees, or complete graphs are characterized. In particular, ▫$\Theta(G)$▫ is complete if and only if ▫$G$▫ can be obtained from ▫$K_1$▫ by a sequence of (newly introduced) dense expansions. ▫$\Theta$▫-graphs are also compared with familiar concepts of crossing graphs and ▫$\tau$▫-graphs.
Ključne besede: mathematics, graph theory, intersection graph, partial cube, median graph, expansion theorem, Cartesian product of graphs
Objavljeno: 31.03.2017; Ogledov: 523; Prenosov: 66
.pdf Celotno besedilo (150,56 KB)
Gradivo ima več datotek! Več...

3.
On graph identification problems and the special case of identifying vertices using paths
Florent Foucaud, Matjaž Kovše, 2012, objavljeni znanstveni prispevek na konferenci

Opis: V članku uvedemo problem identifikacije s potmi: pokritje z identifikacijskimi potmi grafa ▫$G$▫ je množica poti ▫$mathcal{P}$▫, za katere velja, da vsako vozlišče leži na vsaj eni poti iz ▫$mathcal{P}$▫, in za vsak par vozlišč $u,v$ obstaja pot iz ▫$mathcal{P}$▫, ki vsebuje natanko eno izmed vozlišč ▫$u$▫ in ▫$v$▫. Ta problem je soroden raznim variantam identifikacijskih problemov. Problem pokritja z identifikacijskimi potmi obravnavamo na nekaterih družinah grafov. Izpeljemo optimalne velikosti za pokritja z identifikacijskimi potmi za: poti, cikle, hiperkocke in topološka drevesa ter podamo zgornjo mejo za poljubna drevesa. Podamo tudi spodnje in zgornje meje za minimalno velikost pokritja z identifikacijskimi potmi za poljubne grafe in obravnavamo natančnost mej. Pokažemo, da poljuben povezan graf ▫$G$▫ premore pokritje z identifikacijskimi potmi velikosti kvečjemu ▫$Biglceil frac{2(|V(G)|-1)}{3} Bigrceil$▫. Obravnavamo tudi računsko zahtevnost pripadajočega optimizacijskega problema in pokažemo, da v primeru, ko so dolžine poti iz pokritja fiksne dolžine, sodi problem med APX-polne probleme.
Ključne besede: matematika, teorija grafov, poti, aproksimacija, mathematics, graph theory, test cover, identification, paths, approximation
Objavljeno: 10.07.2015; Ogledov: 528; Prenosov: 72
URL Povezava na celotno besedilo

4.
New results on variants of covering codes in Sierpiński graphs
Sylvain Gravier, Matjaž Kovše, Michel Mollard, Julien Moncel, Aline Perreau, 2013, izvirni znanstveni članek

Opis: V prispevku obravnavamo identifikacijske kode, lokalno-dominacijske kode in totalno-dominacijske kode v grafih Sierpińskega. Podani so izračuni minimalnih vrednosti teh kod v grafih Sierpińskega.
Ključne besede: kode v grafih, identifikacijske kode, lokalno-dominacijske kode, totalna-dominacija, grafi Sierpińskega, codes in graphs, identifying codes, locating-dominating codes, total-domination, Sierpiński graphs
Objavljeno: 10.07.2015; Ogledov: 661; Prenosov: 71
URL Povezava na celotno besedilo

5.
Adaptive identification in torii in triangular grids
Matjaž Kovše, Peter Stanet, 2012, izvirni znanstveni članek

Opis: Pri adaptivni identifikaciji postavljamo vprašanja, eno za drugim, pri čemer je dovoljeno postaviti vprašanje, glede na do tistega trenutka prejete odgovore na predhodna vprašanja. Cilj je odkriti (potencialno) okvarjeno vozlišče v grafu. Na adaptivno identifikacijo lahko gledamo tudi kot na igro, kjer prvi igralec skrivoma izbere vozlišče, ki bo okvarjeno, ali ne izbere nobenega vozlišča, drugi igralec pa postavlja vprašanja kot "ali se nahaja okvarjeno vozlišče v krogli $B(v)$ s središčem v vozlišču $v$?" za vozlišča grafa $G$. Cilj prvega igralca je maksimizirati število potrebnih vprašanj. Cilj drugega igralca je minimizirati to število. V članku obravnavamo adaptivno identifikacijo v torusih na trikotniški mreži.
Ključne besede: identifikacijske kode, adaptivna identifikacija, trikotniške mreže, identifying codes, adaptive identification, triangular grids
Objavljeno: 10.07.2015; Ogledov: 813; Prenosov: 11
URL Povezava na celotno besedilo

6.
Extremal graphs for the identifying code problem
Florent Foucaud, Eleonora Guerrini, Matjaž Kovše, Reza Naserasr, Aline Parreau, Petru Valicov, 2011, izvirni znanstveni članek

Opis: Identifikacijska koda grafa ▫$G$▫ je dominacijska množica ▫$C$▫ za katero velja, da se vsako vozlišče ▫$x$▫ iz grafa ▫$G$▫ razlikuje od preostalih vozlišč grafa pomnožici vozlišč iz ▫$C$▫, ki so na razdalji kvečjemu 1 od vozlišča ▫$x$▫. Problem iskanja identifikacijske kode minimalne velikosti se je izkazal za velik izziv. Avtorji N. Bertrand, I. Charon, O. Hudry in A. Lobstein so pokazali, da v primeru grafa na ▫$n$▫ vozliščih in z vsaj eno povezavo, ki premore identifikacijsko kodo, velja, da je velikost minimalne identifikacijske kode kvečjemu ▫$n-1$▫. Podali so tudi razrede grafov, katerih velikost minimalne kode je natanko ▫$n-1$▫. Postavljenih je bilo nekaj domnev v zvezi s karakterizacijo razredov grafov, katerih velikost minimalne kode je natanko ▫$n-1$▫. V članku so ovržene domneve in podana je karakterizacija vseh končnih grafov, ki potrebuje vsa razen enega vozlišča v identifikacijski kodi. Podana je karakterizacija vseh neskončnih grafov, ki potrebuje celotno množico vozlišč za poljubno identifikacijsko kodo. Podane so tudi nove zgornje meje za minimalne identifikacijske kode, ki so izražene z številom vozlišč grafa in maksimalno stopnjo vozlišč v grafu.
Ključne besede: teorija grafov, neskončni grafi, dominacijska množica, identifikacijske kode, graph theory, infinite graphs, domination set, identifying codes
Objavljeno: 10.07.2015; Ogledov: 669; Prenosov: 73
URL Povezava na celotno besedilo

7.
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: 560; Prenosov: 81
URL Povezava na celotno besedilo

8.
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: 10.07.2015; Ogledov: 373; Prenosov: 22
URL Povezava na celotno besedilo

9.
Simultaneous embeddings of graphs as median and antimedian subgraphs
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Sandi Klavžar, Matjaž Kovše, Ajitha R. Subhamathi, 2010, izvirni znanstveni članek

Opis: Razdalja ▫$D_G(v)$▫ vozlišča ▫$v$▫ v grafu ▫$G$▫ je vsota razdalj med ▫$v$▫ in vsemi drugimi vozlišči grafa ▫$G$▫. Množica vozlišč grafa ▫$G$▫ z maksimalno (minimalno) razdaljo je antimedianska (medianska) množica grafa ▫$G$▫. Dokazano je, da za poljubna grafa ▫$G$▫ in ▫$J$▫ ter za poljubno naravno število ▫$r ge 2$▫ obstaja povezani graf ▫$H$▫, tako da je ▫$G$▫ antimedianski in ▫$J$▫ medianski podgraf grafa ▫$H$▫ ter da pri tem velja ▫$d_H(G,J) = r$▫. V primeru, ko sta oba ▫$G$▫ in ▫$J$▫ povezana, lahko dodatno naredimo, da sta ▫$G$▫ in ▫$J$▫ konveksna podgrafa v ▫$H$▫.
Ključne besede: matematika, teorija grafov, problemi razmeščanja, medianske množice, antimedianske množice, konveksni podgrafi, mathematics, graph theory, facility location problems, median sets, antimedian sets, convex subgraphs
Objavljeno: 10.07.2015; Ogledov: 604; Prenosov: 79
URL Povezava na celotno besedilo

10.
On the remoteness function in median graphs
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Wilfried Imrich, Sandi Klavžar, Matjaž Kovše, Ajitha R. Subhamathi, 2009, izvirni znanstveni članek

Opis: Profil grafa ▫$G$▫ je poljubna neprazna multimnožica vozlišč iz ▫$G$▫. Pripadajoča funkcija oddaljenosti priredi vsakemu vozlišču iz ▫$V(G)$▫ vsoto razdalj do vozlišč iz profila. Najprej so dobljene nekatere uporabne lastnosti funkcije oddaljenosti na hiperkockah, nato pa je funkcija oddaljenosti obravnavana na poljubnih medianskih grafih glede na njihove izometrične vložitve v hiperkocke. V posebnem je najdena povezava med vozlišči medianskega grafa ▫$G$▫, katerega funkcija oddaljenosti je največja (antimedianska množica v ▫$G$▫), z antimediansko množico pripadajoče hiperkocke. Medtem ko je za lihe profile antimedianska množica neodvisna množica, ki leži na strogem robu medianskega grafa, obstajajo medianski grafi, v katerih določeni sodi profili porajajo konstantno funkcijo oddaljenosti. Take medianske grafe karakteriziramo na dva načina: kot grafe, katerih periferna transverzala je 2, in kot grafe z geodetskim številom 2. Nazadnje predstavimo algoritem, ki za dani graf ▫$G$▫ z ▫$n$▫ vozlišči in ▫$m$▫ povezavami v času ▫$O(m log n)$▫ odloči, ali je ▫$G$▫ medianski graf z geodetskim številom 2.
Ključne besede: hiperkocka, medianski graf, medianska množica, funkcija oddaljenosti, geodetsko število, periferna transverzala, median graph, median set, remoteness function, geodetic number, periphery transverzal, hypercube
Objavljeno: 10.07.2015; Ogledov: 657; Prenosov: 87
URL Povezava na celotno besedilo

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