Book Embeddings of Regular Graphs
| Autor: | Gelasio Salazar, József Balogh |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Zdroj: | SIAM Journal on Discrete Mathematics. 29:811-822 |
| ISSN: | 1095-7146 0895-4801 |
| DOI: | 10.1137/140961183 |
| Popis: | In the influential paper in which he proved that every graph with $m$ edges can be embedded in a book with $O({m}^{1/2})$ pages, Malitz proved the existence of $d$-regular $n$-vertex graphs that require $\Omega(\sqrt{d}n^{\frac{1}{2}-\frac{1}{d}})$ pages. In view of the $O({m}^{1/2})$ bound, this last bound is tight when $d > \log{n}$, and Malitz asked if it is also tight when $d< \log{n}$. We answer negatively to this question by showing that there exist $d$-regular graphs that require $\Omega(n^{\frac{1}{2}-\frac{1}{2(d-1)}})$ pages. In addition, we show that the bound $O({m}^{1/2})$ is not tight either for most $d$-regular graphs by proving that for each fixed $d$, with high probability the random $d$-regular graph can be embedded in $o({m}^{1/2})$ pages. We also give a simpler proof of Malitz's $O({m}^{1/2})$ bound and improve the proportionality constant. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|