1. Nekatere s pakiranji povezane lastnosti grafovDragana Božović, 2020, doktorska disertacija Opis: V disertaciji se ukvarjamo z različnimi problemi, povezanimi s pakiranji. Disertacija je sestavljena iz štirih delov.
Prvi del je namenjen grafom, ki imajo enolično pakirno množico največje moči. Najprej predstavimo nekatere lastnosti teh grafov. Nato podamo še dve karakterizaciji dreves z enolično pakirno množico.
V drugem delu vpeljemo pojem dimenzije incidenčnosti, ki je neposredno povezana z 2-pakirnim številom grafa, in določimo formulo za njen izračun. Dokažemo, da je problem iskanja incidenčne dimenzije grafa v splošnem NP-poln.
Tretji del namenimo pakirnemu kromatičnemu številu leksikografskega produkta grafov. Določimo njegovo spodnjo in zgornjo mejo ter izboljšano zgornjo mejo za primer, ko je prvi faktor v produktu izomorfen poti.
V zadnjem delu se posvetimo učinkoviti odprti dominaciji produktov digrafov. Okarakteriziramo učinkovito odprto dominirane direktne in leksikografske produkte digrafov. Pri kartezičnem produktu okarakteriziramo tiste, kjer je prvi faktor usmerjena pot, usmerjen cikel ali zvezda z enim izvorom. Predstavimo tudi karakterizacijo učinkovito odprto dominiranega krepkega produkta, katerega temeljni graf obeh faktorjev je monocikličen graf.
Ključne besede: pakirna množica, enolično največje pakiranje, dimenzija incidenčnosti, generator incidenčnosti, pakirno kromatično število, leksikografski produkt grafov, učinkovita odprta dominacija, usmerjeni grafi, produkti usmerjenih grafov
Objavljeno v DKUM: 27.11.2020; Ogledov: 1563; Prenosov: 208
 Celotno besedilo (753,30 KB) |
2. Povezanost v produktih grafovSandra Cigula, 2016, magistrsko delo Opis: V tej nalogi bomo obravnavali pojma povezanost po povezavah in povezanost po vozliščih v produktih grafov. Drugi cilj bo opisati strukturo in ostale lastnosti najmanjših presečnih množic vozlišč in najmanjših presečnih množic povezav v produktih grafov.
Osredotočili se bomo predvsem na kartezični, direktni, krepki in leksikografski produkt grafov. Zanimalo nas bo, kako izraziti povezanost produkta z lastnostmi posameznih faktorjev produkta, kot so najmanjša stopnja, red grafa in povezanost.
Pri direktnem produktu grafov bomo ugotovili, da je povezanost po povezavah odvisna od povezanosti faktorjev, pa tudi od tega, kako daleč sta faktorja $G$ in $H$ od tega, da bi bila dvodelna.
Nato bomo obravnavali velikost in strukturo najmanjših presečnih množic povezav kartezičnih produktov grafov. Podan bo dokaz trditve $lambda(G , Box , H)= textrm{min}left{lambda(G)left|V(H)right|,lambda(H)left|V(G)right|,delta(G)+delta(H)right}.$ Dokaz podobne trditve za povezanost po vozliščih kartezičnega produkta bo naveden v nadaljevanju.
Na koncu bomo obravnavali velikost in strukturo najmanjših presečnih množic povezav krepkih produktov grafov in povezanost v leksikografskem produktu.
Ključne besede: produkti grafov, kartezični produkt, direktni produkt, krepki produkt, leksikografski produkt, povezanost.
Objavljeno v DKUM: 23.08.2016; Ogledov: 1681; Prenosov: 208
Celotno besedilo (3,58 MB) |
3. 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: 121
 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: 88
Povezava na celotno besedilo |
5. 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: 114
Povezava na celotno besedilo |
