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

Abstract

Erdő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ős' work and gave the maximum size $h(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, $h(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.

arXiv comment13 pages, 0 figures. arXiv admin note: text overlap with arXiv:2106.00904