The maximum size of a graph with prescribed order, circumference and minimum degree

Leilei Zhang

Published 2021-07-03Version 1

Erd\H{o}s determined the maximum size of a nonhamiltonian graph of order $n$ and minimum degree at least $k$ in 1962. Recently, Ning and Peng generalized Erd\H{o}s' work and gave the maximum size $\psi(n,c,k)$ of graphs with prescribed order $n$, circumference $c$ and minimum degree at least $k.$ But for some triples $n,c,k,$ the maximum size is not attained by a graph of minimum degree $k.$ For example, $\psi(15,14,3)=77$ is attained by a unique graph of minimum degree $7,$ not $3.$ In this paper we obtain more precise information by determining the maximum size of a graph with prescribed order, circumference and minimum degree. Consequently we solve the corresponding problem for longest paths. All these results on the size of graphs have clique versions.