| | 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 - 10 / 13
First pagePrevious page12Next pageLast page
1.
Maximum independent sets in direct products of cycles or trees with arbitrary graphs
Tjaša Paj, Simon Špacapan, 2015, original scientific article

Abstract: 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.
Keywords: direct product, independent set
Published: 07.04.2017; Views: 802; Downloads: 340
.pdf Full text (173,48 KB)
This document has many files! More...

2.
On acyclic colorings of direct products
Simon Špacapan, Aleksandra Tepeh, 2008, original scientific article

Abstract: 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.
Keywords: mathematics, graph theory, coloring, acyclic coloring, distance-two coloring, direct product
Published: 31.03.2017; Views: 368; Downloads: 62
.pdf Full text (142,13 KB)
This document has many files! More...

3.
Median and quasi-median direct products of graphs
Boštjan Brešar, Pranava Jha, Sandi Klavžar, Blaž Zmazek, 2005, original scientific article

Abstract: 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$▫.
Keywords: mathematics, graph theory, median graph, direct product, quasi-median graph, isometric embeddings, convexity
Published: 31.03.2017; Views: 558; Downloads: 243
.pdf Full text (174,14 KB)
This document has many files! More...

4.
A characterization of the edge connectivity of direct products of graphs
Simon Špacapan, 2013, original scientific article

Abstract: 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.
Keywords: matematika, teorija grafov, direktni produkt, povezanost po povezavah, mathematics, graph theory, direct product, edge connectivity
Published: 10.07.2015; Views: 578; Downloads: 81
URL Link to full text

5.
On the b-chromatic number of some graph products
Marko Jakovac, Iztok Peterin, 2012, original scientific article

Abstract: 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.
Keywords: teorija grafov, b-kromatično število, krepki produkt, leksikografski produkt, direktni produkt, graph theory, b-chromatic number, strong product, lexicographic product, direct product
Published: 10.07.2015; Views: 560; Downloads: 71
URL Link to full text

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

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

7.
Lower bounds for domination and total domination number of direct products graphs
Gašper Mekiš, 2009

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

8.
Perfect codes in direct products of cycles - a complete characterization
Janez Žerovnik, 2008, original scientific article

Abstract: 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.
Keywords: matematika, teorija grafov, korekcijske kode, direktni produkt grafov, popolne kode, cikli, mathematics, graph theory, error-correcting codes, direct product of graphs, perfect codes, cycles
Published: 10.07.2015; Views: 950; Downloads: 70
URL Link to full text

9.
Dominating direct products of graphs
Boštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2007, original scientific article

Abstract: 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.
Keywords: matematika, teorija grafov, dominacija, dominacija v parih, gornja dominacija, kartezični produkt grafov, mathematics, graph theory, domination, paired-domination, upper domination, direct product
Published: 10.07.2015; Views: 618; Downloads: 77
URL Link to full text

10.
An almost complete description of perfect codes in direct products of cycles
Sandi Klavžar, Simon Špacapan, Janez Žerovnik, 2006, original scientific article

Abstract: 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.
Keywords: matematika, teorija grafov, korekcijske kode, direktni produkt grafov, popolne kode, cikli, mathematics, graph theory, error-correcting codes, direct product of graphs, perfect codes, cycles
Published: 10.07.2015; Views: 23493; Downloads: 77
URL Link to full text

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