2.
Extremal graphs for the identifying code problemFlorent 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 v DKUM: 10.07.2015; Ogledov: 1315; Prenosov: 97
Povezava na celotno besedilo
