2008
New infinite families of almost-planar crossing-critical graphs
HLINĚNÝ, PetrZákladní údaje
Originální název
New infinite families of almost-planar crossing-critical graphs
Název česky
Nové nekonečné třídy téměř planárních průsečíkově kritických grafů
Autoři
Vydání
Electronic Journal of Combinatorics, internet, - 2008, 1077-8926
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10101 Pure mathematics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Impakt faktor
Impact factor: 0.586
Kód RIV
RIV/00216224:14330/08:00025241
Organizační jednotka
Fakulta informatiky
UT WoS
000258122700003
Klíčová slova anglicky
crossing-critical; graph
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 1. 6. 2009 13:06, prof. RNDr. Petr Hliněný, Ph.D.
V originále
We show that, for all choices of integers $k>2$ and $m$, there are simple $3$-connected $k$-crossing-critical graphs containing more than $m$ vertices of each even degree $\leq2k-2$. This construction answers one half of a question raised by Bokal, while the other half asking analogously about vertices of odd degrees at least $7$ in crossing-critical graphs remains open. Furthermore, our newly constructed graphs have several other interesting properties; for instance, they are almost planar and their average degree can attain any rational value in the interval $\big[3+\frac15,6-\frac8{k+1}\big)$.
Česky
Ukážeme konstrukci jednoduchých 3-souvislých k-průsečíkově kritických grafů, které obsahují libovolně mnoho vrcholů sudých stupňů <=2k-2 pro všechna k>2. Tato konstrukce zodpovídá jednu polovinu otázky Bokala a má několik dalších zajímavých aplikací.
Návaznosti
| GA201/08/0308, projekt VaV |
| ||
| 1M0545, projekt VaV |
|