Using simulated annealing to construct extremal graphs Original Research Article

The girth of graph G is the length of the shortest cycle in G; if G has no cycle, we define the girth of G as infinite. This paper investigates the values of the maximum number of edges in a graph of order v and girth at least n+1, denoted by ex(v;{C3,C4,…,Cn}). We shall discuss an important property, i.e. the degree distribution of extremal graphs. Then we describe how to integrate this property with the simulated annealing technique to develop an algorithm that can be used to generate extremal graphs. Our algorithm is the first that can be used to generate graphs with girth greater than 5, and it provides lower bounds on ex(v;{C3,C4,…,Cn}) for n⩾6. Some results will be presented.