Camino Balbuena Abstract

An overview on {C_3,…,C_s}-free extremal graphs
Camino Balbuena, Universitat Politecnica de Catalunya, Barcelona, Spain

Abstract
For integers s\ge 4 and n\ge s+1, let ex(n;{C_3,…,C_s}) denote the maximum number of edges in a graph on n vertices and girth at least s+1. We refer to it as the extremal function. By EX(n;{C_3,…,C_s}) we denote the set of all simple graphs of order n, girth at least s+1 and with ex(n;{C_3,…,C_s}) edges. A graph G in EX(n;{C_3,\ldots,C_s}) is called a extremal graph.

Graphs constructed by researches interested in the Cage Problem, provide good constructive lower bounds for the extremal number.

In this talk we will see some exact values of the extremal function for small values of s and also some lower bounds. Moreover, we will revise the last results on the lower bounds on the order of a extremal graph guaranteeing that the girth is equal to s+1 and other
structural properties.

Advertisements