1. Nekaj metričnih lastnosti grafovskih produktovGregor Rus, 2022, doctoral dissertation Abstract: Doktorska disertacija obravnava koncepta množice vozlišč v splošni legi v grafih in l-razdaljno-uravnoteženost grafov. Oba koncepta sta bila v tej obliki vpeljana nedavno, splošna lega leta 2018 v članku avtorjev Manuela in Klavžarja, l-razdaljna uravnoteženost pa v doktorski diseratciji Freliha leta 2014. V disertaciji so predstavljeni novi rezultati, ki so večinoma povezani z različnimi grafovskimi produkti.
Dokazana je točna vrednost gp-števila v kartezičnem produktu poljubnega števila poti, natančneje, da velja $\gp(P^{\cp,n}) = 2^{2^{n-1}}$. Dokazana je točna vrednost gp-števila v produktu poti in cikla in produkta dveh ciklov. Dokazana je tudi točna vrednost gp-števila v nekaterih Kneserjevih grafih.
V razdelku, ki se ukvarja z l-razdaljno-uravnoteženostjo, je pokazan pogoj, kdaj je leksikografski produkt grafov $G[H]$ $\ell$-razdaljno-uravnotežen za poljuben $\ell \in \{3,\ldots,\diam(G)\}$. Prav tako je dokazano, kdaj je $\ell$-razdaljno-uravnotežen korona produkt. Določimo pa tudi pogoj, kdaj je $\ell$-razdaljno uravnotežen kartezični produkt $G\cp K_n.$
Keywords: teorija grafov, množica vozlišč v splošni legi, gp-število, grafovski produkti, poti, cikli, razdaljno-uravnoteženi grafi, l-razdaljno-uravnoteženi grafi
Published in DKUM: 07.10.2022; Views: 785; Downloads: 62
 Full text (965,92 KB) |
2. Neodvisna dominacija na grafihNina Črešnjevec, 2018, master's thesis Abstract: V magistrskem delu obravnavamo različne tipe dominacij in sicer dominantno število, neodvisnostno število, neodvisno dominantno število in zgornje dominantno število. Neodvisno dominantno število je raziskano na različnih družinah grafov kot tudi na različnih grafovskih produktih.
V prvem delu magistrske naloge smo navedli vse pojme, trditve, izreke, ki jih potrebujemo za razumevanje glavnega problema magistrske naloge. Predstavimo tudi različne razrede grafov in različne dominacije v grafih.
V drugem poglavju obravnavamo različne meje neodvisnega dominantnega števila. Predstavljene so splošne meje, ki veljajo na različnih družinah grafov in meje, ki veljajo za dvodelne grafe.
Tretje poglavje pa se nanaša na neodvisno dominantno število krepkega, korenskega in kartezičnega produkta. Za nekatere od teh produktov smo prikazali tudi rezultate o neodvisnostnem številu in dominantnem številu.
Keywords: dominantno število, neodvisno dominantno število, neodvisnostno število, dominantno popolni grafi, dobro pokriti grafi, grafovski produkti
Published in DKUM: 13.07.2018; Views: 1285; Downloads: 134
Full text (1,30 MB) |
3. The edge fault-diameter of Cartesian graph bundlesIztok Banič, Rija Erveš, Janez Žerovnik, 2009, original scientific article Abstract: Kartezični svežnji so posplošitev krovnih grafov in kartezičnih grafovskih produktov. Naj bo ▫$G$▫ nek s povezavami ▫$k_G$▫-povezan graf in ▫${bar{mathcal{D}}_c(G)}$▫ največji premer podgrafov grafa ▫$G$▫ dobljenih z odstranitvijo $▫c < k_G$▫ povezav. Dokazano je, da je ▫${bar{mathcal{D}}_{a+b+1}(G)} le {bar{mathcal{D}}_a(F)} le {bar{mathcal{D}}_b(B)} + 1$▫, če je ▫$G$▫ grafovski sveženj z vlaknom ▫$F$▫ in bazo ▫$B$▫, ▫$a < k_F$▫, ▫$b < k_B▫$. Dokazano je tudi, da je povezanost s povezavami grafovskega svežnja ▫$G▫$ vsaj ▫$k_F + k_B$▫.
Keywords: matematika, teorija grafov, kartezični grafovski produkti, kartezični grafovski svežnji, povezavni okvarni premer, mathematics, graph theory, Cartesian graph products, Cartesian graph bundles, edge-fault diameter
Published in DKUM: 10.07.2015; Views: 1483; Downloads: 92
 Link to full text |
4. Cartesian powers of graphs can be distinguished by two labelsSandi Klavžar, Xuding Zhu, 2007, original scientific article Abstract: The distinguishing number ▫$D(G)$▫ of a graph ▫$G$▫ is the least integer ▫$d$▫ such that there is a ▫$d$▫-labeling of the vertices of ▫$G$▫ which is not preserved by any nontrivial automorphism. For a graph ▫$G$▫ let ▫$G^r$▫ be the ▫$r$▫-th power of ▫$G$▫ with respect to the Cartesian product. It is proved that ▫$D(G^r) = 2$▫ for any connected graph ▫$G$▫ with at least 3 vertices and for any ▫$r = 3$▫. This confirms and strengthens a conjecture of Albertson. Other graph products are also considered and a refinement of the Russell and Sundaram motion lemma is proved.
Keywords: matematika, teorija grafov, razlikovalno število, grafovski avtomorfizem, produkti grafov, mathematics, graph theory, distingushing number, graph automorphism, products of graphs
Published in DKUM: 10.07.2015; Views: 1260; Downloads: 88
Link to full text |
5. Distinguishing Cartesian powers of graphsWilfried Imrich, Sandi Klavžar, 2006, original scientific article Abstract: Razlikovalno število ▫$D(G)$▫ grafa je najmanjše celo število ▫$d$▫, za katero obstaja taka ▫$d$▫-označitev točk grafa ▫$G$▫, da je ne ohranja noben avtomorfizem grafa ▫$G$▫. Dokažemo, da je razlikovalno število kvadrata in višjih potenc povezanega grafa ▫$G ne K_2, K_3$▫, glede na kartezični produkt, vedno enako 2. Ta rezultat je močnejši od rezultatov Albertsona [Electron J Combin, 12 (2005), N17] za potence pra-grafov in tudi od rezultatov Klavžarja and Zhuja [European J. Combin, v tisku]. Bolj splošno, dokažemo tudi, da je ▫$(G Box H) = 2$▫, če sta ▫$G$▫ in ▫$H$▫ relativno tuja grafa in je ▫$|H| le |G| < 2^{|H|} - |H|$▫. Pod podobnimi pogoji veljajo sorodni rezultati tudi za potence grafov glede na krepki in direktni produkt grafov.
Keywords: matematika, teorija grafov, razlikovalno število, grafovski avtomorfizem, produkti grafov, mathematics, graph theory, distingushing number, graph automorphism, products of graphs
Published in DKUM: 10.07.2015; Views: 1234; Downloads: 97
Link to full text |
6. On the k-path vertex cover of some graph productsMarko Jakovac, Andrej Taranenko, 2013, original scientific article Abstract: A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. Denote by ▫$psi_k$▫(G) the minimum cardinality of a k-path vertex cover in G. In this paper, improved lower and upper bounds for ▫$psi_k$▫ of the Cartesian and the strong product of paths are derived. It is shown that for ▫$psi_3$▫ those bounds are tight. For the lexicographic product bounds are presented for ▫$psi_k$▫, moreover ▫$psi_2$▫ and ▫$psi_3$▫ are exactly determined for the lexicographic product of two arbitrary graphs. As a consequence the independence and the dissociation number of the lexicographic product are given.
Keywords: matematika, teorija grafov, vozliščno pokritje, po poteh vozliščno pokritje, disociacijsko število, neodvisnostno število, grafovski produkti, mathematics, graph theory, vertex cover, path vertex cover, dissociation number, independence number, graph products
Published in DKUM: 10.07.2015; Views: 1486; Downloads: 28
Link to full text |
