Article ID Journal Published Year Pages File Type
420224 Discrete Applied Mathematics 2010 10 Pages PDF
Abstract

For integers n≥4n≥4 and ν≥n+1ν≥n+1, let ex(ν;{C3,C4,…,Cn})ex(ν;{C3,C4,…,Cn}) denote the maximum number of edges in a graph with νν vertices and girth at least n+1n+1. In this paper we have obtained bounds on this function for n∈{5,6,7}n∈{5,6,7} and, in several cases, even the exact value. We have also developed a greedy algorithm for generating graphs with large size for given order and girth.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,