-
Structural approach to the crossing number of graphs : doctoral thesisBokal, 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.Type of material - dissertationPublication and manufacture - Ljubljana : [D. Bokal], 2006Language - english, slovenianCOBISS.SI-ID - 14039129
Author
Bokal, Drago, 1978-
Other authors
Mohar, Bojan, 1956-
Topics
teorija grafov |
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)
Library | Call number – location, accession no. ... | Copy status |
---|---|---|
National and University Library, Ljubljana | GS II 619589 glavno skladišče | available - reading room |
Central Technological Library of the University of Ljubljana | 52047/1635 Skladišče IN: 320060122 |
available - outside loan, loan period: 14 days |
FMF, Mathematical Library, Lj. | Skladišče-Jadranska 21 10921/91 |
available - reading room |
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Bokal, Drago, 1978- | 22402 |
Mohar, Bojan, 1956- | 01931 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.