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

On extremal bipartite graphs with high girth

on Electronic Notes in Discrete M... Jan 01, 2006

Extremal non-bipartite regular graphs of girth 4

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

Extremal non-bipartite regular graphs of girth 4

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

Extremal Regular Graphs with Prescribed Odd Girth

on Journal of Combinatorial Theor... Jan 01, 1994
More articles like this..