On extremal graphs with bounded girth | NOVA. The University of Newcastle's Digital Repository

Home

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/808406

Title: On extremal graphs with bounded girth
Author/Creator: Delorme, Charles; Flandrin, Evelyne; Lin, Yuqing; Miller, Mirka; Ryan, Joe
Institution: The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
Description: By the extremal number ex(n;t) = ex(n;{C₃,C₄,…,Ct}) 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.
Relation: Electronic Notes in Discrete Mathematics Vol. 34, p. 653-657
Publisher Link: http://dx.doi.org/10.1016/j.endm.2009.07.110
Date: 2009
Publisher: Elsevier
Keyword(s): extremal graph; extremal number; forbidden cycles; size; girth
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/808406
Identifier: ISSN:1571-0653

17 Visitors

18 Hits

NOVA. The University of Newcastle's Digital Repository