1. Edge-transitive lexicographic and cartesian productsWilfried Imrich, Ali Iranmanesh, Sandi Klavžar, Abolghasem Soltani, 2016, izvirni znanstveni članek Opis: In this note connected, edge-transitive lexicographic and Cartesian products are characterized. For the lexicographic product ▫$G \circ H$▫ of a connected graph ▫$G$▫ that is not complete by a graph ▫$H$▫, we show that it is edge-transitive if and only if ▫$G$▫ is edge-transitive and ▫$H$▫ is edgeless. If the first factor of ▫$G \circ H$▫ is non-trivial and complete, then ▫$G \circ H$▫ is edge-transitive if and only if ▫$H$▫ is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang, Xu, and Zhao (Appl. Math. Lett. 24 (2011) 1924--1926). For the Cartesian product it is shown that every connected Cartesian product of at least two non-trivial factors is edge-transitive if and only if it is the Cartesian power of a connected, edge- and vertex-transitive graph.
Ključne besede: edge-transitive graph, vertex-transitive graph, lexicographic product of graphs, Cartesian product of graphs
Objavljeno v DKUM: 31.03.2017; Ogledov: 1072; Prenosov: 441
 Celotno besedilo (150,33 KB)
Gradivo ima več datotek! Več... |
2. Some Steiner concepts on lexicographic products of graphsBijo S. Anand, Manoj Changat, Iztok Peterin, Prasanth G. Narasimha-Shenoi, 2012, izvirni znanstveni članek Opis: The smallest tree that contains all vertices of a subset ▫$W$▫ of ▫$V(G)$▫ is called a Steiner tree. The number of edges of such a tree is the Steiner distance of ▫$W$▫ and union of all Steiner trees of ▫$W$▫ form a Steiner interval. Both of them are described for the lexicographic product in the present work. We also give a complete answer for the following invariants with respect to the Steiner convexity: the Steiner number, the rank, the hull number, and the Carathéodory number, and a partial answer for the Radon number. At the end we locate and repair a small mistake from [J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, On the geodetic and the hull numbers in strong product graphs, Comput. Math. Appl. 60 (2010) 3020--3031].
Ključne besede: teorija grafov, leksikografski produkt, Steinerjeva konveksnost, Steinerjeva množica, Steinerjeva razdalja, graph theory, lexicographic product, Steiner convexity, Steiner set, Steiner distance
Objavljeno v DKUM: 10.07.2015; Ogledov: 1219; Prenosov: 117
 Povezava na celotno besedilo |
3. On the b-chromatic number of some graph productsMarko 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: 1190; Prenosov: 90
Povezava na celotno besedilo |
4. The pre-hull number and lexicographic productIztok Peterin, 2012, objavljeni znanstveni prispevek na konferenci Opis: Nedavno sta Polat in Sabidussi v [On the geodesic pre-hull number of a graph, Europ. J. Combin. 30 (2009), 1205--1220] vpeljala invarianto ko-točkovno pred-ovojnično število ▫$mathrm{ph}(G)$▫ grafa ▫$G$▫, ki meri nekonveksnost konveksnega prostora. Vpeljemo podobno invarianto imenovano konveksno pred-ovojnično število, ki je naravna zgornja meja za ko-točkovno pred-ovojnično število. Obe invarianti študiramo na leksikografskem produktu in podamo natančne vrednosti za obe invarianti glede na lastnosti faktorjev.
Ključne besede: matematika, teorija grafov, pred-ovojnično število, geodetska konveksnost, leksikografski produkt, mathematics, graph theory, pre-hull number, geodesic convexity, lexicographic product
Objavljeno v DKUM: 10.07.2015; Ogledov: 1070; Prenosov: 86
Povezava na celotno besedilo |
5. The geodetic number of the lexicographic product of graphsBoštjan Brešar, Tadeja Kraner Šumenjak, Aleksandra Tepeh, 2011, izvirni znanstveni članek Opis: Množica ▫$S$▫ vozlišč grafa ▫$G$▫ je geodetska, če vsako vozlišče grafa ▫$G$▫ leži na intervalu med dvema vozliščema iz ▫$S$▫. Velikost najmanjše geodetske množice grafa ▫$G$▫ se imenuje geodetsko število ▫$g(G)$▫ grafa ▫$G$▫. V članku dokažemo, da geodetsko število leksikografskega produkta ▫$G circ H$▫, kjer ▫$H$▫ ni poln graf, leži med 2 in ▫$3g(G)$▫. Okarakteriziramo vse grafe ▫$G$▫ in ▫$H$▫, za katere je ▫$G circ H = 2$▫, kot tudi leksikografske produkte ▫$T circ H$▫, za katere je ▫$g(T circ H) = 3g(G)$▫, kjer je ▫$T$▫ izomorfen drevesu. Z uporabo novega koncepta geodominantnih trojic grafa ▫$G$▫ najdemo formulo, ki določi točno geodetsko število ▫$G circ H$▫, kjer je ▫$G$▫ poljuben graf in ▫$H$▫ graf, ki ni poln.
Ključne besede: matematika, teorija grafov, leksikografski produkt, geodetsko število, geodominantna trojica, mathematics, graph theory, lexicographic product, geodetic number, geodominating triple
Objavljeno v DKUM: 10.07.2015; Ogledov: 1137; Prenosov: 91
Povezava na celotno besedilo |
6. Rainbow domination in the lexicographic product of graphsTadeja Kraner Šumenjak, Douglas F. Rall, Aleksandra Tepeh, 2013, izvirni znanstveni članek Opis: Preslikava iz množice vozlišč grafa ▫$G$▫ v potenčno množico množice ▫${1,2,dots, k}$▫ se imenuje ▫$k$▫-mavrična dominantna funkcija, če za poljubno vozlišče ▫$v$▫ z lastnostjo ▫$f(v) = emptyset$▫ velja ▫${1,dots,k} = bigcup_{u in N(v)}f(u)$▫. Obravnavamo ▫$k$▫-mavrično dominantno število grafa ▫$G$▫, ▫$gamma_{rk}(G)$▫, ki je minimalna vsota (po vseh vozliščih grafa ▫$G$▫) moči podmnožic, ki so vozliščem dodeljena s ▫$k$▫-mavrično dominantno funkcijo. V članku se osredotočimo na 2-mavrično dominantno število leksikografskega produkta grafov in dokažemo natančno spodnjo in zgornjo mejo za to število. Dejansko pokažemo natančno vrednost za ▫$gamma_{r2}(G circ H)$▫, razen v primeru, ko je ▫$gamma_{r2}(H) = 3$▫ in obstaja taka minimalna 2-mavrična dominantna funkcija grafa $H$, ki nekemu vozlišču v grafu ▫$H$▫ dodeli oznako ▫${1,2}$▫.
Ključne besede: dominacija, popolna dominacija, mavrična dominacija, leksikografski produkt, domination, total domination, rainbow domination, lexicographic product
Objavljeno v DKUM: 10.07.2015; Ogledov: 1355; Prenosov: 114
Povezava na celotno besedilo |
7. On the Roman domination in the lexicographic product of graphsTadeja Kraner Šumenjak, Polona Repolusk, Aleksandra Tepeh, 2012, izvirni znanstveni članek Opis: A Roman dominating function of a graph ▫$G = (V,E)$▫ is a function ▫$f colon V to {0,1,2}$▫ such that every vertex with ▫$f(v) = 0$▫ is adjacent to some vertex with ▫$f(v) = 2$▫. The Roman domination number of ▫$G$▫ is the minimum of ▫$w(f) = sum_{v in V}f(v)$▫ over all such functions. Using a new concept of the so-called dominating couple we establish the Roman domination number of the lexicographic product of graphs. We also characterize Roman graphs among the lexicographic product of graphs.
Ključne besede: teorija grafov, rimska dominacija, popolna dominacija, leksikografski produkt, graph theory, Roman domination, total domination, lexicographic product
Objavljeno v DKUM: 10.07.2015; Ogledov: 1844; Prenosov: 110
Povezava na celotno besedilo |
8. |
