On Degree Properties of Crossing-Critical Families of Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00108270" target="_blank" >RIV/00216224:14330/19:00108270 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p53/7812" target="_blank" >https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p53/7812</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.37236/7753" target="_blank" >10.37236/7753</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Degree Properties of Crossing-Critical Families of Graphs

Popis výsledku v původním jazyce

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) &gt;= 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.

Název v anglickém jazyce

On Degree Properties of Crossing-Critical Families of Graphs

Popis výsledku anglicky

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) &gt;= 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA17-00837S" target="_blank" >GA17-00837S: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Electronic Journal of Combinatorics

ISSN

1077-8926

e-ISSN

—

Svazek periodika

26

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

28

Strana od-do

1-28

Kód UT WoS článku

000463559900011

EID výsledku v databázi Scopus

—