On Degree Properties of Crossing-Critical Families of Graphs

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

BOKAL Drago BRACIC Mojca DERŇÁR Marek HLINĚNÝ Petr

Rok publikování 2019
Druh Článek v odborném periodiku
Časopis / Zdroj Electronic Journal of Combinatorics
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p53/7812
Doi http://dx.doi.org/10.37236/7753
Klíčová slova graph theory; crossing number; crossing-critical
Popis Answering an open question from 2007, we construct infinite k-crossing-critical families of graphs that contain vertices of any prescribed odd degree, for any sufficiently large k. To answer this question, we introduce several properties of infinite families of graphs and operations on the families allowing us to obtain new families preserving those properties. This conceptual setup allows us to answer general questions on behaviour of degrees in crossing-critical graphs: we show that, for any set of integers D such that min(D) >= 3 and 3, 4 is an element of D, and for any sufficiently large k, there exists a k-crossing-critical family such that the numbers in D are precisely the vertex degrees that occur arbitrarily often in (large enough) graphs of this family. Furthermore, even if both D and some average degree in the interval (3, 6) are prescribed, k-crossing-critical families exist for any sufficiently large k.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.