| | 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 - 3 / 3
First pagePrevious page1Next pageLast page
1.
New results on variants of covering codes in Sierpiński graphs
Sylvain Gravier, Matjaž Kovše, Michel Mollard, Julien Moncel, Aline Perreau, 2013, original scientific article

Abstract: 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.
Keywords: 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
Published: 10.07.2015; Views: 626; Downloads: 71
URL Link to full text

2.
Adaptive identification in torii in triangular grids
Matjaž Kovše, Peter Stanet, 2012, original scientific article

Abstract: 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.
Keywords: identifikacijske kode, adaptivna identifikacija, trikotniške mreže, identifying codes, adaptive identification, triangular grids
Published: 10.07.2015; Views: 779; Downloads: 10
URL Link to full text

3.
Extremal graphs for the identifying code problem
Florent Foucaud, Eleonora Guerrini, Matjaž Kovše, Reza Naserasr, Aline Parreau, Petru Valicov, 2011, original scientific article

Abstract: 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.
Keywords: teorija grafov, neskončni grafi, dominacijska množica, identifikacijske kode, graph theory, infinite graphs, domination set, identifying codes
Published: 10.07.2015; Views: 646; Downloads: 72
URL Link to full text

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