-
Structural approach to the crossing number of graphs : doctoral thesis = Strukturni pristop k prekrižnemu številu grafov : doktorska disertacijaBokal, Drago, 1978-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.Vrsta gradiva - disertacijaZaložništvo in izdelava - Ljubljana : [D. Bokal], 2006Jezik - angleški, slovenskiCOBISS.SI-ID - 14039129
Avtor
Bokal, Drago, 1978-
Drugi avtorji
Mohar, Bojan, 1956-
Teme
matematika |
teorija grafov |
disertacije |
prekrižno število |
prekrižno-kritičen graf |
povprečna stopnja |
kartezični produkt |
zvezda |
pot |
drevo |
kolo |
minorsko prekrižno število |
grafovski minor |
graph theory |
crossing number |
crossing-critical graph |
average degree |
Cartesian product |
star |
path |
tree |
whell |
minor crossing number |
graph minor
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Signatura – lokacija, inventarna št. ... |
Status izvoda | Rezervacija |
---|---|---|
Skladišče II 0000063816 Skladišče II 63816 |
prosto - za čitalnico
|
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Bokal, Drago, 1978- | 22402 |
Mohar, Bojan, 1956- | 01931 |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.