Maximizing the size of planar graphs under girth constraints

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F14%3A43924758" target="_blank" >RIV/49777513:23520/14:43924758 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Maximizing the size of planar graphs under girth constraints

Popis výsledku v původním jazyce

In 1975, Erdős proposed the problem of determining the maximal number of edges in a graph on n vertices that contains no triangles or squares. In this paper we consider a generalized version of the problem, i.e., what is the maximum size of a graph of order n and girth at least t+1 (containing no cycles of length less than t + 1). We consider the problem on special types of graphs, such as pseudotrees, cacti, graphs lying in a square grid, Halin, generalized Halin and planar graphs. We give the extremalcases, some constructions and we use these results to obtain general lower bounds for the problem in the general case.

Název v anglickém jazyce

Maximizing the size of planar graphs under girth constraints

Popis výsledku anglicky

In 1975, Erdős proposed the problem of determining the maximal number of edges in a graph on n vertices that contains no triangles or squares. In this paper we consider a generalized version of the problem, i.e., what is the maximum size of a graph of order n and girth at least t+1 (containing no cycles of length less than t + 1). We consider the problem on special types of graphs, such as pseudotrees, cacti, graphs lying in a square grid, Halin, generalized Halin and planar graphs. We give the extremalcases, some constructions and we use these results to obtain general lower bounds for the problem in the general case.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2014

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

Journal of Combinatorial Mathematics and Combinatorial Computing

ISSN

0835-3026

e-ISSN

—

Svazek periodika

89

Číslo periodika v rámci svazku

Neuveden

Stát vydavatele periodika

CA - Kanada

Počet stran výsledku

13

Strana od-do

129-141

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—