| OPOMBE | Nasl. str. tudi v slov.: Strukturni pristop k prekrižnemu številu grafov : doktorska disertacija // Mentor Bojan Mohar //Bibliografija: str. 97-107 // Kazalo // Povzetek ; Abstract // Univ. Ljubljana, Fakulteta za matematiko in fiziko, Oddelek za matematiko // Raziskovanje prekrižno-kritičnih grafov je začel Širáň, ki je za vsak cel ▫$k \ge 3$▫ konstruiral neskončno družino ▫$3$▫-povezanih ▫$k$▫-prekrižno-kritičnih grafov. Kochol je za vsak cel ▫$k \ge 2$▫ konstruiral neskončno družino enostavnih ▫$3$▫-povezanih ▫$k$▫-prekrižno-kritičnih grafov. Richter in Thomassen sta začela s študijem stopenj vozlišč v prekrižno-kritičnih grafih, ko sta pokazala, da za vsaka cela ▫$r \ge 6$▫ in ▫$k \ge 1$▫ obstaja le končno mnogo ▫$k$▫-prekrižno-kritičnih grafov z minimalno stopnjo ▫$r$▫. Salazar je opazil, da iz njunega argumenta sledi obstoj le končno mnogo ▫$k$▫-prekrižno-kritičnih grafov s povprečno stopnjo ▫$r$▫ za vsak cel ▫$k \ge 1$▫ in vsak racionalen ▫$r>6$▫. Pokazal je, da za vsak racionalen ▫$r \in (4,6)$▫ obstaja tako zaporedje ▫$\{k_{r,i}\}_{i=0}^{\infty}$▫, da za vsak ▫$i \in \NN$▫ obstaja neskončna družina ▫$k_{r,i}$▫-prekrižno-kritičnih grafov s povprečno stopnjo ▫$r$▫, in vprašal po obstoju takih družin za ▫$r \in (3,4)$▫. Na vprašanje sta delno pozitivno odgovorila Pinontoan in Richter,ki sta razvila teorijo tlakovcev in z njeno pomočjo konstruirala iskane družine za $r \in (3\frac{1}{2},4)$▫. V disertaciji nadgradimo njuno delo,da omogoči posplošitev prekrižno-kritičnih grafov, ki jih je konstruiral Kochol. Kombinacija teorije tlakovcev in nove operacije na grafih in njihovih risbah, šiva, nam omogoči popoln odgovor na Salazarjevo vprašanjein njegovopovezavo z rezultati Širáňa in Kochola v obliki naslednjega izreka: obstajataka zvezna konveksna funkcija $f:(3,6) \to \RR^+$▫, da za vsako racionalnoštevilo ▫$r \in (3,6)$▫ in vsako celo število ▫$k \ge f(r)$▫ obstaja neskončna družina prekrižno-kritičnih grafov s povprečno stopnjo ▫$r$▫ in prekrižnim številom ▫$k$▫. Beineke in Ringeisen sta raziskovala prekrižno število kartezičnih produktov malih grafov in ciklov ter določila natančne vrednosti za vse ▫$C_n \Box G$▫, kjer je ▫$G$▫ poljuben graf reda štiri, razen ▫$3$▫-zvezda ▫$K_{1,3}$▫. Jendrol' in Ščerbová sta zapolnila to vrzel. Ugotovila sta tudi prekrižno število ▫$P_m \Box K_{1,3}$▫ in postavila domnevo za splošen rezultat o $P_m \Box K_{1,n}$▫. Domnevo je za ▫$n = 4$▫ dokazal Klešč. V nekoliko splošnejši različici jo za vsak ▫$n \ge3$▫ dokažemo v pričujočem delu: rezultat Asana o prekrižnem številu grafa ▫$K_{1,3,n}$▫ povežemo z operacijo šiv in dobimo prekrižno število grafa $T\Box K_{1,n}$▫, kjer je ▫$T$▫ poljubno drevo z maksimalno stopnjo tri in ▫$n \ge 3$▫ poljubno celo število. Ta rezultat dopolnimo s prekrižnim številom grafov ▫$T \Box K_{1,3}$▫ za poljubno drevo ▫$T$▫, prekrižnim številom grafov ▫$P_m \Box W_n$▫ za poljubna ▫$m \ge 1$▫, ▫$n \ge 3$▫, ter več drugimi eksaktnimi rezultati in mejami. Seymour je obžaloval, da prekrižno število ne sodeluje na naraven način s teorijo grafovskih minorjev: stiskanje povezave lahko vrednost te invariante poveča ali zmanjša. V tem delu uvedemo minorsko prekrižno število. To je minorsko monotona invarianta, ki omogoča dodatno zmanjševanje števila križišč v risbi, tako da vozlišča zamenjamo z z drevesi in minimiziramo število križišč v risbah vseh takih grafov. Ta invarianta ima bolj naravne uporabe pri izdelavi elektronskih vezij kot navadno prekrižno število. V delu pokažemo več splošnih mej za njeno vrednost, raziščemo strukturo grafov z omejenim minorskim prekrižnim številom in predstavimo nekaj eksaktnih rezultatov in mej za posamezne družine grafov. Ena od spodnjih mej je posplošitev rezultata Morene in Salazarja, ki sta prekrižno število grafa omejila s prekrižnim številom njegovega minorja z majhno maksimalno stopnjo. // Crossing-critical graphs were introduced by Širáň, who proved existence of infinite families of ▫$3$▫-connected ▫$k$▫-crossing-critical graphs for every ▫$k \ge 3$▫. Kochol proved existence of infinite families of simple ▫$3$▫-connected ▫$k$▫-crossing-critical graphs, ▫$k \ge 2$▫. Richter and Thomassen started the research on degrees in crossing-critical graphs by proving that there are only finitely many simple ▫$k$▫-crossing-critical graphs with minimum degree ▫$r$▫ for every two integers ▫$r \ge 6$▫ and ▫$k \ge 1$▫. Salazar observed that their argument implies the same conclusion for every rational ▫$r>6$▫, integer ▫$k \ge 1$▫, and simple ▫$k$▫-crossing-critical graphs with average degree ▫$r$▫. For every rational ▫$r \in [4,6)$▫ he proved existence of an infinite sequence ▫$\{k_{r,i}\}_{i=0}^{\infty}$▫ such that for every ▫$i \in \NN$▫ there exists an infinite family of simple ▫$4$▫-connected ▫$k_{r,i}$▫-crossing-critical graphs with average degree ▫$r$▫ and asked about existence of such families for rational ▫$r \in (3,4)$▫. The questionwas partially resolved by Pinontoan and Richter, who answered it positivelyfor ▫$r \in (3\frac{1}{2},4)$▫. In the present work we extend the theory oftiles, developed by Pinontoan and Richter, to encompass a generalization ofthe crossing-critical graphs constructed by Kochol. Combining tiles with a new graph operation, the zip product, which preserves the crossing number of the involved graphs, we settle the question of Salazar and combine the answer with the results of Širáň and Kochol into the following theorem: there exists a convex continuous function ▫$f:(3,6) \to \RR^+$▫, such that,for every rational number ▫$r \in (3,6)$▫ and every integer ▫$k \ge f(r)$▫,there exists an infinite family of simple ▫$3$▫-connected crossing-criticalgraphs with average degree ▫$r$▫ and crossing number ▫$k$▫. Beineke and Ringeisen investigated the crossing numbers of Cartesian products of small graphs with cycles and established the crossing numbers of the Cartesian product of ▫$C_n \Box G$▫ where ▫$G$▫ is any simple graph of order four, except the ▫$3$▫-star, ▫$K_{1,3}$▫. Jendrol' and Ščerbová closed this gap and also obtained the crossing number of ▫$P_m \Box K_{1,3}$▫. They conjectured the general result for $P_m \Box K_{1,n}$▫, which was proven for ▫$n=4$▫ by Klešč. We prove their conjecture in a slightly more general setting: by combining the result of Asano about the crossing number of ▫$K_{1,3,n}$▫ with the zip product, we establish the crossing number of ▫$T\Box K_{1,n}$▫ where ▫$T$▫ is any tree of maximum degree three and ▫$n \ge 3$▫ is any integer. We supplement this result by the crossing number of ▫$T\Box K_{1,3}$▫ for any tree ▫$T$▫, the crossing number of $P_m \Box W_n$▫ for any ▫$m \ge 1$▫, ▫$n \ge 3$▫, and some other exact results and bounds. Seymour regretted that the crossing number does not work well with graph minors, as the contraction of an edge can both increase and decrease the value of this graph invariant. We introduce the minor crossing number, a minor-monotone graph invariant that allows for further minimization of the number of crossings by allowing replacement of vertices by trees and minimizing the number of crossings in the resulting graph. We argue that this graph invariant is more natural in the VLSI applications than the ordinary crossing number, prove several general lower bounds on the minor crossing number, study the structure of graphs with bounded minor crossing number and provide some exact results and bounds for specific graphs. In particular, we generalize a result of Moreno and Salazar, who bounded the crossing number of a graph from below using the crossing number of its minor of small maximum degree.Način dostopa (URN): http://www.dlib.si/?urn=URN:NBN:SI:doc-6L3NRC6N |