1. Celotna in neodvisna mavrična dominacija : na študijskem programu 2. stopnje MatematikaAnja Petek, 2021, magistrsko delo Opis: V magistrskem delu predstavimo novi različici mavrične dominacije, celotno in neodvisno mavrično dominacijo. Podobno kot pri mavrični dominaciji sta tudi ti dve inačici povezani s posplošenimi prizmami $G\square K_k$. Slednje predstavljajo kartezični produkt poljubnega grafa $G$ in polnega grafa $K_k$. V delu podamo nekaj mej in lastnosti $k$-mavričnega celotnega dominantnega števila $\gamma_{\rtk}(G)$, ter $k$-mavričnega neodvisnega dominantnega števila $\gamma_{\rik}(G)$. Za nekatere znane družine grafov predstavimo tudi natančne vrednosti. Na koncu dela sledi Nordhaus-Gaddumov tip rezultata neodvisne mavrične dominacije za $k=2$, $5\leq \gamma_{\ridva}(G)+\gamma_{\ridva}(\overline{G})\leq n+3$, kjer $\overline{G}$ predstavlja komplement grafa $G$.
Ključne besede: dominacija, kartezični produkt, mavrična dominacija, celotna mavrična dominacija, neodvisna mavrična dominacija, Nordhaus-Gaddum
Objavljeno v DKUM: 05.01.2022; Ogledov: 914; Prenosov: 51
 Celotno besedilo (618,19 KB) |
2. 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: 187
Celotno besedilo (753,30 KB) |
3. Dominacija v grafih in ravninski grafi pri pouku v osnovni in srednji šoliIlija Ilić, 2018, magistrsko delo Opis: V magistrskem delu so predstavljene izbrane vsebine iz teorije grafov s poudarkom na dominacijah v grafih in na ravninskih grafih. V teoretičnem delu so navedene vse potrebne definicije, izreki, trditve in dokazi obravnavanih vsebin, poleg tega pa je predstavljena tudi didaktična teorija o izvajanju pouka.
V praktičnem delu so nato predstavljeni primeri izbranih obravnav omenjenih vsebin pri pouku v osnovnih in srednjih šolah. Vsebine so zastavljene kot celovita osnova za nadaljnje načrtovanje učnih priprav in zajemajo teoretične razlage, naloge z grafičnim gradivom in rešitvami ter didaktične nasvete za predstavitev vsebin.
Ključne besede: dominacija v grafih, ravninski grafi, teorija grafov pri pouku v osnovni in srednji šoli
Objavljeno v DKUM: 27.09.2018; Ogledov: 1340; Prenosov: 133
Celotno besedilo (2,37 MB) |
4. Učinkovita odprta dominacija na grafovskih produktihMiha Soršak, 2016, diplomsko delo Opis: Diplomsko delo obravnava učinkovito odprto dominacijo na grafovskih produktih. Zraven natančnega opisa pojma učinkovite odprte dominacije so obravnavani še ostali pojmi in trditve, ki jih uporabimo pri utemeljitvi poglavitnih izrekov. V diplomskem delu pokažemo, kateri so potrebni in zadostni pogoji za učinkovito odprto dominianacijo grafov med direktnimi, leksikografskimi, krepkimi in disjunktnimi produkti. Za kartezični produkt je vključenih nekaj delnih rezultatov o učinkoviti odprti dominaciji torusov in cilindrov.
Ključne besede: učinkovita odprta dominacija, leksikografski produkt, direktni produkt, kartezični produkt
Objavljeno v DKUM: 11.11.2016; Ogledov: 1575; Prenosov: 165
Celotno besedilo (462,68 KB) |
5. New results on variants of covering codes in Sierpiński graphsSylvain Gravier, Matjaž Kovše, Michel Mollard, Julien Moncel, Aline Perreau, 2013, izvirni znanstveni članek Opis: V prispevku obravnavamo identifikacijske kode, lokalno-dominacijske kode in totalno-dominacijske kode v grafih Sierpińskega. Podani so izračuni minimalnih vrednosti teh kod v grafih Sierpińskega.
Ključne besede: kode v grafih, identifikacijske kode, lokalno-dominacijske kode, totalna-dominacija, grafi Sierpińskega, codes in graphs, identifying codes, locating-dominating codes, total-domination, Sierpiński graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 1302; Prenosov: 95
 Povezava na celotno besedilo |
6. A note on the domination number of the Cartesian products of paths and cyclesPolona Repolusk, Janez Žerovnik, 2011 Opis: Z uporabo algebraičnega pristopa implementiramo konstantni algoritem za računanje dominantnega števila kartezičnih produktov poti in ciklov. Podamo formule za dominantna števila ▫$gamma(P_n Box C_k)$▫ (za ▫$k leq 11$▫, ▫$n in {mathbb N}$)▫ in dominantna števila ▫$gamma(C_n Box P_k)$▫ in ▫$gamma(C_n Box C_k)$▫ (za ▫$k leq 6$▫, ▫$n in {mathbb N}$▫).
Ključne besede: teorija grafov, kartezični produkt, grid, torus, dominacija, algebra poti, konstantni algoritem, graph theory, Cartesian product, grid graph, torus, graph domination, path algebra, constant time algorithm
Objavljeno v DKUM: 10.07.2015; Ogledov: 1740; Prenosov: 40
Povezava na celotno besedilo |
7. Vizing's conjecture: a survey and recent resultsBoštjan Brešar, Paul Dorbec, Wayne Goddard, Bert L. Hartnell, Michael A. Henning, Sandi Klavžar, Douglas F. Rall, 2012, pregledni znanstveni članek Opis: Vizingova domneva iz leta 1968 trdi, da je dominacijsko število kartezičnega produkta dveh grafov vsaj tako veliko, kot je produkt dominacijskih števil faktorjev. V članku naredimo pregled različnih pristopov k tej osrednji domnevi iz teorije grafovske dominacije. Ob tem dokažemo tudi nekaj novih rezultatov. Tako so na primer pokazane nove lastnosti minimalnega protiprimera, dokazana je tudi nova spodnja meja za produkte grafov brez induciranega ▫$K_{1,3}$▫ s poljubnimi grafi. Skozi celoten članek so obravnavani pripadajoči odprti problemi, vprašanja in sorodne domneve.
Ključne besede: matematika, teorija grafov, kartezični produkt, dominacija, Vizingova domneva, mathematics, graph theory, Caretesian product, domination, Vizing's conjecture
Objavljeno v DKUM: 10.07.2015; Ogledov: 1362; Prenosov: 90
Povezava na celotno besedilo |
8. Vizing's conjecture: a survey and recent resultsBoštjan Brešar, Paul Dorbec, Wayne Goddard, Bert L. Hartnell, Michael A. Henning, Sandi Klavžar, Douglas F. Rall, 2009 Opis: Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this paper we survey the approaches to this central conjecture from domination theory and give some new results along the way. For instance, several new properties of a minimal counterexample to the conjecture are obtained and a lower bound for the domination number is proved for products of claw-free graphs with arbitrary graphs. Open problems, questions and related conjectures are discussed throughout the paper.
Ključne besede: matematika, teorija grafov, kartezični produkt, dominacija, Vizingova domneva, mathematics, graph theory, Caretesian product, domination, Vizing's conjecture
Objavljeno v DKUM: 10.07.2015; Ogledov: 1365; Prenosov: 99
Povezava na celotno besedilo |
9. Fair reception and Vizing's conjectureBoštjan Brešar, Douglas F. Rall, 2009, izvirni znanstveni članek Opis: Vpeljemo koncept poštenega sprejema grafa, ki je povezan z njegovim dominantnim številom. Dokažemo, da za vse grafe, ki imajo pošten sprejem velikosti njihovega dominantnega števila, velja Vizingova domneva o dominantnem številu kartezičnega produkta grafov, s čimer posplošimo dobro znan rezultat Barcalkina in Germana o razstavljivih grafih. S kombiniranjem nav sega koncepta in rezultata Aharonija, Bergerja in Ziva dobimo alternativen dokaz izreka Aharonija in Szaba, ki pravi, da tetivni grafi zadoščajo Vizingovi domnevi. Predstavimo tudi novo neskončno družino grafov, ki zadoščajo Vizingovi domnevi.
Ključne besede: matematika, teorija grafov, dominacija, kartezični produkt grafov, Vizingova domneva, mathematics, graph theory, domination, Cartesian product of graphs, Vizing's conjecture
Objavljeno v DKUM: 10.07.2015; Ogledov: 1254; Prenosov: 113
Povezava na celotno besedilo |
10. Dominating direct products of graphsBoš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: 1240; Prenosov: 98
Povezava na celotno besedilo |
