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 and Petr HLINĚNÝ

Basic information

Original name

On Degree Properties of Crossing-Critical Families of Graphs

Authors

BOKAL, Drago (705 Slovenia), Mojca BRACIC (705 Slovenia), Marek DERŇÁR (703 Slovakia, belonging to the institution) and Petr HLINĚNÝ (203 Czech Republic, belonging to the institution)

Edition

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

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

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

References:

URL

Impact factor

Impact factor: 0.641

RIV identification code

RIV/00216224:14330/19:00108270

Organization unit

Faculty of Informatics

DOI

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

UT WoS

000463559900011

Keywords in English

graph theory; crossing number; crossing-critical

Abstract

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.

Links

GA17-00837S, research and development project

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

Investor: Czech Science Foundation

Citovat

BOKAL, Drago, Mojca BRACIC, Marek DERŇÁR and Petr HLINĚNÝ. On Degree Properties of Crossing-Critical Families of Graphs. Electronic Journal of Combinatorics. internet: -, 2019, vol. 26, No 1, p. 1-28. ISSN 1077-8926. Available from: 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 and Petr HLINĚNÝ. On Degree Properties of Crossing-Critical Families of Graphs. \textit{Electronic Journal of Combinatorics}. internet: -, 2019, vol.~26, No~1, p.~1-28. ISSN~1077-8926. Available from: https://dx.doi.org/10.37236/7753.

Detailed Information on Publication Record