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

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1178/725" target="_blank" >http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1178/725</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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&gt;=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ázev v anglickém jazyce

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

Popis výsledku anglicky

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

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

—

Návaznosti

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

Acta Math. Univ. Comenianae

ISSN

0231-6986

e-ISSN

0862-9544

Svazek periodika

88

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

SK - Slovenská republika

Počet stran výsledku

7

Strana od-do

787-793

Kód UT WoS článku

000484349000067

EID výsledku v databázi Scopus

2-s2.0-85073795597