SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:Nekateri rezultati o povezanosti in neodvisnih množicah v produktih grafov
Avtorji:Paj Erker, Tjaša (Avtor)
Špacapan, Simon (Mentor) Več o mentorju... Novo okno
Datoteke:.pdf DOK_Paj_Erker_Tjasa_2018.pdf (603,74 KB)
 
Jezik:Slovenski jezik
Vrsta gradiva:Doktorsko delo/naloga (mb31)
Tipologija:2.08 - Doktorska disertacija
Organizacija:FNM - Fakulteta za naravoslovje in matematiko
Opis:Doktorska disertacija obravnava nekatere rezultate na grafovskih produktih. V uvodu bomo na kratko predstavili vsebino doktorske disertacije in ponovili nekatere osnovne pojme teorije grafov, ki jih bomo uporabljali v nadaljevanju. Prva tema, ki jo bomo predstavili so neodvisne množice v direktnem produktu. Govorili bomo o velikosti in strukturi največjih neodvisnih množic v direktnem produktu. Najprej bomo predstavili pomembnejše znane rezultate, nato pa bomo pokazali, da ima direkten produkt lihe poti in poljubnega grafa, ter direkten produkt sodega cikla in poljubnega grafa največjo neodvisno množico, ki je unija dveh pravokotnikov. Ugotovili bomo, da obstajajo v direktnem produktu sode poti in poljubnega grafa največje neodvisne množice, ki so lahko tudi drugačne oblike ter zapisali natančno karakterizacijo teh največjih neodvisnih množic. Zapisali bomo zadostni pogoji za drevesa, da ima direkten produkt drevesa in poljubnega grafa največjo neodvisno množico oblike dveh pravokotnikov. V nadaljevanju bomo raziskali posplošeno 3-povezanost v kartezičnem produktu grafov. Prikazali bomo več naravnih načinov, kako dobiti 3-presečno množico S, pri kateri nam graf razpade na vsaj tri komponente. Nato bomo dokazali, da je eden izmed teh načinov vedno optimalen, če sta G in H 2-povezana grafa na vsaj šestih vozliščih. Tako dobimo natančno vrednost posplošene 3-povezanosti kartezičnega produkta dveh 2-povezanih grafov na vsaj šestih vozliščih. Na koncu se bomo ukvarjali z vprašanjem o zgornji meji najmanjšega diametra krepko orientiranega krepkega produkta. Določili bomo natančno vrednost najmanjšega diametra krepkega produkta dveh poti.
Ključne besede:direktni produkt, kartezični produkt, krepki produkt, neodvisna množica, povezanost, posplošena povezanost, diameter, krepka orientacija
Leto izida:2018
Založnik:T. Paj Erker]
Izvor:[Maribor
UDK:519.171(043.3)
COBISS_ID:297733120 Povezava se odpre v novem oknu
Licenca:CC BY-NC-ND 4.0
To delo je dosegljivo pod licenco Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
Število ogledov:104
Število prenosov:24
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:FNM
:
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Some results on connectivity and independent sets in product graphs
Opis:We study the independence number of direct products of graphs, and the structure of maximum independent sets in them. We prove that every product of an odd path or an even cycle with an arbitrary graph has a maximum independent set which is a union of two rectangles. We show that for an even path, might have independent sets that are not equal to an union of two rectangles, and give a characterization of such maximum independent sets. In the sequel we study the generalized k-connectivity of Cartesian products of graphs. We show several natural ways how to split a graph into three connected components by the removal of vertices. We determine the minimum cardinality of a vertex 3-cut in G□H for any 2-connected graphs G and H on at least six vertices. For graphs G and H we find an upper bound for the minimum diameter of a strong orientation of G⊠H. We prove that Pm⊠Pn admits an optimal orientation for m,n>=5, m≠n. This is a strong orientation, such that the diameter of the directed graph.
Ključne besede:direct product, Cartesian product, strong product, independent set, connectivity, generalized connectivity, diameter, strong orientation


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici