Další formáty:
BibTeX
LaTeX
RIS
@article{818374, author = {Hliněný, Petr}, article_location = {internet}, article_number = {1}, keywords = {crossing-critical; graph}, language = {eng}, issn = {1077-8926}, journal = {Electronic Journal of Combinatorics}, title = {New infinite families of almost-planar crossing-critical graphs}, url = {http://www.combinatorics.org/Volume_15/PDF/v15i1r46.pdf}, volume = {15}, year = {2008} }
TY - JOUR ID - 818374 AU - Hliněný, Petr PY - 2008 TI - New infinite families of almost-planar crossing-critical graphs JF - Electronic Journal of Combinatorics VL - 15 IS - 1 SP - R102 EP - R102 PB - - SN - 10778926 KW - crossing-critical KW - graph UR - http://www.combinatorics.org/Volume_15/PDF/v15i1r46.pdf N2 - 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)$. ER -
HLINĚNÝ, Petr. New infinite families of almost-planar crossing-critical graphs. \textit{Electronic Journal of Combinatorics}. internet: -, 2008, roč.~15, č.~1, s.~R102, 12 s. ISSN~1077-8926.
|