doktorska disertacija
Povzetek
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, tj. oblike ▫$(A \times C) \cup (B \times D)$▫. 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 ▫$(A \times C) \cup (B \times D)$▫. 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 ▫$G \Box H \backslash S$▫ 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 ▫$G \boxtimes H$▫. Določili bomo natančno vrednost najmanjšega diametra krepkega produkta ▫$P_m \boxtimes P_n$▫ za ▫$m, n \ge 5$▫.
Ključne besede
disertacije;direktni produkt;kartezični produkt;krepki produkt;neodvisne množice;povezanost;posplošena povezanost;diameter;krepka orientacija;
Podatki
Jezik: |
Slovenski jezik |
Leto izida: |
2018 |
Tipologija: |
2.08 - Doktorska disertacija |
Organizacija: |
UM FNM - Fakulteta za naravoslovje in matematiko |
Založnik: |
T. Paj Erker] |
UDK: |
519.171(043.3) |
COBISS: |
297733120
|
Št. ogledov: |
932 |
Št. prenosov: |
101 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Angleški jezik |
Sekundarni naslov: |
Some results on connectivity and independent sets in product graphs |
Sekundarni povzetek: |
In this thesis we study connectivity and independent sets in product graphs. in the introduction we briefly describe the topic of the dissertation and define basic concepts of graph theory. 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, more precisely, a set of the form ▫$I = (A \times C) \cup (B \times D)$▫. We show that for an even ▫$n$▫, ▫$P_n \times G$▫ might have independent sets that are not equal to an union of two rectangles, and give a characterization of maximum independent subsets of ▫$P_n \times G$▫ for every even ▫$n$▫. We also give a sufficient condition for a tree ▫$T$▫, so that ▫$T \times G$▫ has a maximum independent set of the form ▫$I = (A \times C) \cup (B \times D)$▫. 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 \Box 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 \boxtimes H$▫. We prove that ▫$P_m \boxtimes P_n$▫ admits an optimal orientation for ▫$m, n \ge 5, m \ne n$▫. This is a strong orientation, such that the diameter of the directed graph is equal to the diameter of the underlying undirected graph. |
Sekundarne ključne besede: |
dissertations;direct product;Cartesian product;strong product;independent set;connectivity;generalized connectivity;diameter;strong orientation;Grafi;Disertacije;Produkti; |
URN: |
URN:SI:UM: |
Vrsta dela (COBISS): |
Doktorsko delo/naloga |
Komentar na gradivo: |
Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo |
Strani: |
IX, 91 str. |
ID: |
10940364 |