Affordable Access

Publisher Website

On Extremal Graphs with Bounded Girth

Authors
Journal
Electronic Notes in Discrete Mathematics
1571-0653
Publisher
Elsevier
Publication Date
Volume
34
Identifiers
DOI: 10.1016/j.endm.2009.07.110
Keywords
  • Extremal Graph
  • Extremal Number
  • Forbidden Cycles
  • Size
  • Girth

Abstract

Abstract By the extremal number ex ( n ; t ) = ex ( n ; { C 3 , C 4 , … , C t } ) we denote the maximum size (number of edges) in a graph of n vertices, n > t , and girth (length of shortest cycle) at least g ⩾ t + 1 . In 1975, Erdős proposed the problem of determining the extremal numbers ex ( n ; 4 ) of a graph of n vertices and girth at least 5. In this paper, we consider a generalized version of this problem, for t ⩾ 5 . In particular, we prove that ex ( n ; 6 ) for n = 29 , 30 and 31 is equal to 45, 47 and 49, respectively.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Extremal Regular Graphs with Prescribed Odd Girth

on Journal of Combinatorial Theor... Jan 01, 1994

On extremal bipartite graphs with high girth

on Electronic Notes in Discrete M... Jan 01, 2006
More articles like this..