Article ID Journal Published Year Pages File Type
1708927 Applied Mathematics Letters 2012 5 Pages PDF
Abstract

For integers n≥4n≥4 and ν≥n+1ν≥n+1, let ex(ν;{C3,…,Cn})ex(ν;{C3,…,Cn}) denote the maximum number of edges in a graph of order νν and girth at least n+1n+1. The {C3,…,Cn}{C3,…,Cn}-free graphs with order νν and size ex(ν;{C3,…,Cn})ex(ν;{C3,…,Cn}) are called extremal graphs and denoted by EX(ν;{C3,…,Cn})EX(ν;{C3,…,Cn}). We prove that given an integer k≥0k≥0, for each n≥2log2(k+2)n≥2log2(k+2) there exist extremal graphs with νν vertices, ν+kν+k edges and minimum degree 1 or 2. Considering this idea we construct four infinite families of extremal graphs. We also see that minimal (r;g)(r;g)-cages are the exclusive elements in EX(ν0(r,g);{C3,…,Cg−1})EX(ν0(r,g);{C3,…,Cg−1}).

Related Topics
Physical Sciences and Engineering Engineering Computational Mechanics
Authors
, ,