1. Distance formula for direct-co-direct product in the case of disconnected factorsAleksander Kelenc, Iztok Peterin, 2023, izvirni znanstveni članek Opis: Direktni-ko-direktni produkt ▫$G\circledast H$▫ grafov ▫$G$▫ in ▫$H$▫ je graf na množizi vozlišč ▫$V(G)\times V(H)$▫. Vozlišči ▫$(g,h)$▫ in ▫$(g',h')$▫ sta sosednji, če je ▫$gg'\in E(G)$▫ in ▫$hh'\in E(H)$▫ ali ▫$gg'\notin E(G)$▫ in ▫$hh'\notin E(H)$▫. Naj bo največ eden izmed faktorjev ▫$G$▫ in ▫$H$▫ povezan. Pokažemo da je razdalja med dvema vozliščema v ▫$G\circledast H$▫ omejena s tri, razen v majhnem številu izjem. Vse izjeme so natančno popisane, kar prinese razdaljno formulo za ▫$G\circledast H$▫.
Ključne besede: direktni-ko-direktni produkt, razdalja, ekscentričnost, nepovezan graf, direct-co-direct product, distance, eccentricity, disconnected graphs
Objavljeno v DKUM: 21.05.2024; Ogledov: 115; Prenosov: 6
 Celotno besedilo (449,36 KB)
Gradivo ima več datotek! Več... |
2. Lower bounds for domination and total domination number of direct products graphsGašper Mekiš, 2009 Opis: An exact lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: ▫$gamma(times_{i=1}^t K_{n_i} ge t+1$▫, ▫$t ge 3$▫. Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: ▫$gamma(G times H) ge gamma(G) + gamma(H) - 1$▫. Infinite families of graphs that attain the bound are presented. For these graphs it also holds ▫$gamma_t(G times H) = gamma(G) + gamma(H) - 1$▫. Some additional parallels with the total domination number are made.
Ključne besede: matematika, teorija grafov, dominacijska množica, dominacijsko število, celotna dominacijska množica, celotno dominacijsko število, direktni produkt grafov, poln graf, mathematics, graph theory, dominating set, domination number, total dominating set, total domination number, direct product graphs, complete graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 1305; Prenosov: 41
 Povezava na celotno besedilo |
3. Perfect codes in direct products of cycles - a complete characterizationJanez Žerovnik, 2008, izvirni znanstveni članek Opis: Let ▫$G = times^n_{i=1}C_{ell_i}$▫ be a direct product of cycles. It is known that for any ▫$r le 1$▫, and any ▫$n le 2▫$, each connected component of ▫$G$▫ contains a so-called canonical ▫$r$▫-perfect code provided that each ▫$ell_i$▫ is a multiple of ▫$r^n + (r+1)^n$▫. Here we prove that up to a reasonably defined equivalence, these are the only perfect codes that exist.
Ključne besede: matematika, teorija grafov, korekcijske kode, direktni produkt grafov, popolne kode, cikli, mathematics, graph theory, error-correcting codes, direct product of graphs, perfect codes, cycles
Objavljeno v DKUM: 10.07.2015; Ogledov: 1886; Prenosov: 92
Povezava na celotno besedilo |
4. An almost complete description of perfect codes in direct products of cyclesSandi Klavžar, Simon Špacapan, Janez Žerovnik, 2006, izvirni znanstveni članek Opis: Naj bo ▫$G = times_{i=1}^nC_{ell_i}$▫ direktni produkt ciklov. Dokazano je, da za vsak ▫$r ge 1$▫ in za vsak ▫$n ge 2$▫ velja naslednje. Če je vsak ▫$ell_i$▫ večkratnik od ▫$r^n + (r+1)^n$▫, tedaj vsaka povezana komponenta grafa ▫$G$▫ vsebuje ▫$r$▫-popolno kodo. Po drugi strani je tudi dokazano, da če koda grafa ▫$G$▫ vsebuje izbrano točko in njene lokalno kanonične točke, tedaj je vsak ▫$ell_i$▫ večkratnik od ▫$r^n + (r+1)^n$▫. Nadalje je dokazano, da je ▫$r$▫-popolna koda ▫$(r ge 2)$▫ grafa ▫$G$▫ enolično določena z ▫$n$▫ točkami. Postavljena je domneva, da za ▫$r ge 2$▫ ne obstajajo nobene druge kode v $G$ razen tistih, ki so konstruirane v članku.
Ključne besede: matematika, teorija grafov, korekcijske kode, direktni produkt grafov, popolne kode, cikli, mathematics, graph theory, error-correcting codes, direct product of graphs, perfect codes, cycles
Objavljeno v DKUM: 10.07.2015; Ogledov: 24186; Prenosov: 101
Povezava na celotno besedilo |
