TY - JOUR

T1 - Maximizing the size of planar graphs under girth constraints

AU - Christou, Michalis

AU - Iliopoulos, Costas S.

AU - Miller, Mirka

PY - 2014

Y1 - 2014

N2 - In 1975, Erdos 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, ex(n;t), of a graph of order n and girth at least t + 1 (containing no cycles of length less than t +1). The set of those extremal Ct-free graphs is denoted by EX(n;t). 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 extremal cases, some constructions and we use these results to obtain general lower bounds for the problem in the general case.

AB - In 1975, Erdos 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, ex(n;t), of a graph of order n and girth at least t + 1 (containing no cycles of length less than t +1). The set of those extremal Ct-free graphs is denoted by EX(n;t). 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 extremal cases, some constructions and we use these results to obtain general lower bounds for the problem in the general case.

UR - http://www.scopus.com/inward/record.url?scp=84902075192&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84902075192

SN - 0835-3026

VL - 89

SP - 129

EP - 141

JO - Journal of Combinatorial Mathematics and Combinatorial Computing

JF - Journal of Combinatorial Mathematics and Combinatorial Computing

ER -