Opombe
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 njegovo povezavo z rezultati Širáňa in Kochola v obliki naslednjega izreka: obstaja taka 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 \ge 3$? 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.
doktorska disertacija