On Degree Properties of Crossing-Critical Families of Graphs

J 2019

On Degree Properties of Crossing-Critical Families of Graphs

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

Základní údaje

Originální název

On Degree Properties of Crossing-Critical Families of Graphs

Autoři

BOKAL, Drago (705 Slovinsko), Mojca BRACIC (705 Slovinsko), Marek DERŇÁR (703 Slovensko, domácí) a Petr HLINĚNÝ (203 Česká republika, domácí)

Vydání

Electronic Journal of Combinatorics, internet, - 2019, 1077-8926

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.641

Kód RIV

RIV/00216224:14330/19:00108270

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.37236/7753

UT WoS

000463559900011

Klíčová slova anglicky

graph theory; crossing number; crossing-critical

Štítky

formela-journal

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 11. 6. 2022 00:15, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Návaznosti

GA17-00837S, projekt VaV

Název: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech

Investor: Grantová agentura ČR, Structural properties, parameterized tractability and hardness in combinatorial problems

Citovat

BOKAL, Drago, Mojca BRACIC, Marek DERŇÁR a Petr HLINĚNÝ. On Degree Properties of Crossing-Critical Families of Graphs. Electronic Journal of Combinatorics. internet: -, 2019, roč. 26, č. 1, s. 1-28. ISSN 1077-8926. Dostupné z: https://dx.doi.org/10.37236/7753.

@article{1646039,
   author = {Bokal, Drago and Bracic, Mojca and Derňár, Marek and Hliněný, Petr},
   article_location = {internet},
   article_number = {1},
   doi = {http://dx.doi.org/10.37236/7753},
   keywords = {graph theory; crossing number; crossing-critical},
   language = {eng},
   issn = {1077-8926},
   journal = {Electronic Journal of Combinatorics},
   title = {On Degree Properties of Crossing-Critical Families of Graphs},
   url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p53/7812},
   volume = {26},
   year = {2019}
}

TY  - JOUR
ID  - 1646039
AU  - Bokal, Drago - Bracic, Mojca - Derňár, Marek - Hliněný, Petr
PY  - 2019
TI  - On Degree Properties of Crossing-Critical Families of Graphs
JF  - Electronic Journal of Combinatorics
VL  - 26
IS  - 1
SP  - 1-28
EP  - 1-28
PB  - -
SN  - 10778926
KW  - graph theory
KW  - crossing number
KW  - crossing-critical
UR  - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p53/7812
L2  - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p53/7812
N2  - 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.
ER  -

BOKAL, Drago, Mojca BRACIC, Marek DERŇÁR a Petr HLINĚNÝ. On Degree Properties of Crossing-Critical Families of Graphs. \textit{Electronic Journal of Combinatorics}. internet: -, 2019, roč.~26, č.~1, s.~1-28. ISSN~1077-8926. Dostupné z: https://dx.doi.org/10.37236/7753.

Podrobný výpis o publikaci