| | 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 / 13
Na začetekNa prejšnjo stran12Na naslednjo stranNa konec
1.
Maximum independent sets in direct products of cycles or trees with arbitrary graphs
Tjaša Paj, Simon Špacapan, 2015, izvirni znanstveni članek

Opis: The direct product of graphs ▫$G = (V(G),E(G))$▫ and ▫$H = (V(H),E(H))$▫ is the graph, denoted as ▫$G \times H$▫, with vertex set ▫$V(G \times H) = V(G )\times V(H)$▫, where vertices ▫$(x_1,y_1)$▫ and ▫$(x_2,y_2)$▫ are adjacent in ▫$G \times H$▫ if ▫$x_1x_2 \in E(G)$▫ and ▫$y_1y_2 \in E(H)$▫. Let ▫$n$▫ be odd and ▫$m$▫ even. We prove that every maximum independent set in ▫$P_n \times G$▫, respectively ▫$C_m \times G$▫, is of the form ▫$(A \times C) \cup (B \times D)$▫, where ▫$C$▫ and ▫$D$▫ are nonadjacent in ▫$G$▫, and ▫$A \cup B$▫ is the bipartition of ▫$P_n$▫ respectively ▫$C_m$▫. We also give a characterization of maximum independent subsets of ▫$P_n \times G$▫ for every even ▫$n$▫ and discuss the structure of maximum independent sets in ▫$T \times G$▫ where ▫$T$▫ is a tree.
Ključne besede: direct product, independent set
Objavljeno v DKUM: 07.04.2017; Ogledov: 923; Prenosov: 387
.pdf Celotno besedilo (173,48 KB)
Gradivo ima več datotek! Več...

2.
On acyclic colorings of direct products
Simon Špacapan, Aleksandra Tepeh, 2008, izvirni znanstveni članek

Opis: A coloring of a graph ▫$G$▫ is an acyclic coloring if the union of any two color classes induces a forest. It is proved that the acyclic chromatic number of direct product of two trees ▫$T_1$▫ and ▫$T_2$▫ equals ▫$\min\{ \Delta(T_1) + 1, \Delta(T_2) + 1\}$▫. We also prove that the acyclic chromatic number of direct product of two complete graphs ▫$K_m$▫ and ▫$K_n$▫ is ▫$mn-m-2$▫, where ▫$m \ge n \ge 4$▫. Several bounds for the acyclic chromatic number of direct products are given and in connection to this some questions are raised.
Ključne besede: mathematics, graph theory, coloring, acyclic coloring, distance-two coloring, direct product
Objavljeno v DKUM: 31.03.2017; Ogledov: 497; Prenosov: 69
.pdf Celotno besedilo (142,13 KB)
Gradivo ima več datotek! Več...

3.
Median and quasi-median direct products of graphs
Boštjan Brešar, Pranava Jha, Sandi Klavžar, Blaž Zmazek, 2005, izvirni znanstveni članek

Opis: Median graphs are characterized among direct products of graphs on at least three vertices. Beside some trivial cases, it is shown that one component of ▫$G \times P_3$▫ is median if and only if ▫$G$▫ is a tree in that the distance between any two vertices of degree at least 3 is even. In addition, some partial results considering median graphs of the form ▫$G \times K_2$▫ are proved, and it is shown that the only nonbipartite quasi-median direct product is ▫$K_3 \times K_3$▫.
Ključne besede: mathematics, graph theory, median graph, direct product, quasi-median graph, isometric embeddings, convexity
Objavljeno v DKUM: 31.03.2017; Ogledov: 699; Prenosov: 274
.pdf Celotno besedilo (174,14 KB)
Gradivo ima več datotek! Več...

4.
A characterization of the edge connectivity of direct products of graphs
Simon Špacapan, 2013, izvirni znanstveni članek

Opis: V članku dokažemo formulo za povezanost po povezavah direktnega produkta grafov. V formuli se povezanost po povezavah produkta izraža kot funkcija povezanosti po povezavah, najmanjše stopnje, števila povezav in dvodelne frustracije obeh faktorjev. Prav tako v članku opišemo strukturo najmanjših presečnih množic v direktnih produktih grafov.
Ključne besede: matematika, teorija grafov, direktni produkt, povezanost po povezavah, mathematics, graph theory, direct product, edge connectivity
Objavljeno v DKUM: 10.07.2015; Ogledov: 695; Prenosov: 87
URL Povezava na celotno besedilo

5.
On the b-chromatic number of some graph products
Marko Jakovac, Iztok Peterin, 2012, izvirni znanstveni članek

Opis: Pravilno barvanje vozlišč grafa kjer vsak barvni razred vsebuje vozlišče, ki ima soseda v vseh preostalih barvnih razredih, imenujemo b-barvanje. Največje naravno število ▫$varphi (G)$▫, za katero obstaja b-barvanje grafa ▫$G$▫, imenujemo b-kromatično število. Določimo nekatere spodnje in zgornje meje b-kromatičnega števila za krepki produkt ▫$G,boxtimes, H$▫, leksikografski produkt ▫$G[H]$▫ in za direktni produkt ▫$G,times, H$▫. Prav tako določimo nekatere točne vrednosti za produkte poti, ciklov, zvezd in polnih dvodelnih grafov. Pokažemo tudi, da lahko določimo b-kromatično število za ▫$P_n ,boxtimes, H$▫, ▫$C_n ,boxtimes, H$▫, ▫$P_n[H]$▫, ▫$C_n[H]$▫ in ▫$K_{m,n}[H]$▫ za poljuben graf ▫$H$▫, če sta le ▫$m$▫ in ▫$n$▫ dovolj veliki.
Ključne besede: teorija grafov, b-kromatično število, krepki produkt, leksikografski produkt, direktni produkt, graph theory, b-chromatic number, strong product, lexicographic product, direct product
Objavljeno v DKUM: 10.07.2015; Ogledov: 683; Prenosov: 75
URL Povezava na celotno besedilo

6.
On connectivity and hamiltonicity of direct graph bundles
Irena Hrastnik Ladinek, Janez Žerovnik, 2011

Opis: A necessary and sufficient condition for connectedness of direct graph bundles where the fibers are cycles is given. It is also proved that all connected direct graph bundles ▫$X=C_stimes^{alpha}C_t$▫ are Hamiltonian.
Ključne besede: direktni produkt grafov, direktni grafovski sveženj, hamiltonski graf, povezan graf, direct graph product, Cartesian graph bundle, Hamiltonian graph, connected graph, reflection, cyclic ▫$ell$▫-shift
Objavljeno v DKUM: 10.07.2015; Ogledov: 643; Prenosov: 24
URL Povezava na celotno besedilo

7.
Lower bounds for domination and total domination number of direct products graphs
Gaš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: 756; Prenosov: 32
URL Povezava na celotno besedilo

8.
Perfect codes in direct products of cycles - a complete characterization
Janez Ž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: 1109; Prenosov: 76
URL Povezava na celotno besedilo

9.
Dominating direct products of graphs
Boštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2007, izvirni znanstveni članek

Opis: Dokazana je zgornja meja za dominantno število direktnega produkta grafov. V posebnem primeru iz meje sledi, da za poljubna grafa ▫$G$▫ in ▫$H$▫ velja ▫$gamma (G times H) le 3gamma(G)gamma(H)$▫. Konstruirani so grafi s poljubno velikimi dominantnimi števili, za katere je ta meja dosežena. Za gornje dominantno število dokažemo, da velja ▫$Gamma(G times H) ge Gamma(G)Gamma(H)$▫, s čimer je potrjena domneva iz [R. Nowakowski, D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79]. Nazadnje za dominacijo v parih direktnih produktov dokažemo, da za poljubna grafa ▫$G$▫ in ▫$H$▫ velja ▫$gamma_{rm{pr}}(G times H) le gamma_{rm{pr}} (G)gamma_{rm{pr}}(H)$▫. Predstavimo tudi neskončne družine grafov, pri katerih je ta meja dosežena.
Ključne besede: matematika, teorija grafov, dominacija, dominacija v parih, gornja dominacija, kartezični produkt grafov, mathematics, graph theory, domination, paired-domination, upper domination, direct product
Objavljeno v DKUM: 10.07.2015; Ogledov: 752; Prenosov: 83
URL Povezava na celotno besedilo

10.
An almost complete description of perfect codes in direct products of cycles
Sandi 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: 23649; Prenosov: 82
URL Povezava na celotno besedilo

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