J 2019

On the achievable average degrees in 2-crossing-critical graphs

HLINĚNÝ, Petr a Michal KORBELA

Základní údaje

Originální název

On the achievable average degrees in 2-crossing-critical graphs

Autoři

HLINĚNÝ, Petr ORCID a Michal KORBELA

Vydání

Acta Math. Univ. Comenianae, 2019, 0231-6986

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Slovensko

Utajení

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

Odkazy

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/19:00112160

Organizační jednotka

Fakulta informatiky

UT WoS

EID Scopus

Klíčová slova anglicky

graph; crossing number; crossing-critical

Štítky

Změněno: 6. 5. 2020 17:14, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

c-Crossing-critical graphs are the minimal graphs requiring at least c edge crossings in every drawing in the plane. The structure of these obstructions is very rich for every c>=2. Although, at least in the first nontrivial case of c=2, their structure is well understood. For example, we know that, aside of finitely many small exceptions, the 2-crossing-critical graphs have vertex degrees from the set {3, 4, 5, 6} and their average degree can achieve exactly all rational values from the interval [3+1/2 , 4+2/3]. Continuing in depth in this research direction, we determine which average degrees of 2-crossing-critical graphs are possible if we restrict their vertex degrees to proper subsets of {3, 4, 5, 6}. In particular, we identify the (surprising) subcases in which, by number-theoretical reasons, the achievable average degrees form discontinuous sets of rationals.

Návaznosti

MUNI/A/1018/2018, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VIII.
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VIII., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty