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