20.500.12556/DKUM-70734 Nekateri rezultati o povezanosti in neodvisnih množicah v produktih grafov Some results on connectivity and independent sets in product graphs 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. 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. direktni produkt kartezični produkt krepki produkt neodvisna množica povezanost posplošena povezanost diameter krepka orientacija direct product Cartesian product strong product independent set connectivity generalized connectivity diameter strong orientation true true false T. Paj Erker] Slovenski jezik Angleški jezik Doktorsko delo/naloga 2018-06-11 10:55:58 2018-12-11 13:37:19 2022-08-01 19:44:59 2019-07-11 18:18:03 2018 0 [Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.171(043.3) 297733120 URN:SI:UM:DK:D9ISO1AH DOK_Paj_Erker_Tjasa_2018.pdf DOK_Paj_Erker_Tjasa_2018.pdf 1 C65739E32C06F33FF33139397AD7277F e6dcac9616bab2487a51f743bf36422205680503d2456f61c4adec3bdede1f37 84049d3f-7c10-11eb-bb7a-00155d0001ca 20.500.12556/dkum/e7a4976e-dfb6-4698-82fb-112977d4eca7 https://dk.um.si/Dokument.php?lang=slv&id=131559 Fakulteta za naravoslovje in matematiko 0 0 0