Extremal Graphs with Girth Nine

摘要

For integers s >= 4 and n >= s + 1, let ex(n; s) denote the maximum number of edges in a graph with n vertices and girth at least s+1, and EX (n; s) denote the set of extremal graphs. For s = 8, the values of ex(n; s) for n <= 24 are known. In this paper, we characterize the graphs in EX(n; 8) for n = 13, 16, 18, 22 and 26, and determine the exact values of ex(n; 8) for 25 <= n <= 30, in which the result ex(25; 8) = 31 corrects a small error in Marshall's paper [Electronic Notes in Discrete Mathematics 38 (2011) 615-620]. Moreover, we improve lower bounds on ex(n; 8) for 31 <= n <= 57 based on three special graphs.