2021•arXiv (Cornell University)Open access
The maximum size of a graph with prescribed order, circumference and minimum degree
Leilei Zhang
Open full text 0 citations
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.
Open-access reader