Back to Search Start Over

A stability version for a theorem of Erd��s on nonhamiltonian graphs

Authors :
F��redi, Zolt��n
Kostochka, Alexandr
Luo, Ruth
Publication Year :
2016
Publisher :
arXiv, 2016.

Abstract

Let $n, d$ be integers with $1 \leq d \leq \left \lfloor \frac{n-1}{2} \right \rfloor$, and set $h(n,d):={n-d \choose 2} + d^2$ and $e(n,d):= \max\{h(n,d),h(n, \left \lfloor \frac{n-1}{2} \right \rfloor)\}$. Because $h(n,d)$ is quadratic in $d$, there exists a $d_0(n)=(n/6)+O(1)$ such that $e(n,1)> e(n, 2)> \dots >e(n,d_0)=e(n, d_0+1)=\dots = e(n,\left \lfloor \frac{n-1}{2} \right \rfloor)$. A theorem by Erd��s states that for $d\leq \left \lfloor \frac{n-1}{2} \right \rfloor$, any $n$-vertex nonhamiltonian graph $G$ with minimum degree $��(G) \geq d$ has at most $e(n,d)$ edges, and for $d > d_0(n)$ the unique sharpness example is simply the graph $K_n-E(K_{\lceil (n+1)/2\rceil})$. Erd��s also presented a sharpness example $H_{n,d}$ for each $1\leq d \leq d_0(n)$. We show that if $d< d_0(n)$ and a $2$-connected, nonhamiltonian $n$-vertex graph $G$ with $��(G) \geq d$ has more than $e(n,d+1)$ edges, then $G$ is a subgraph of $H_{n,d}$. Note that $e(n,d) - e(n, d+1) = n - 3d - 2 \geq n/2$ whenever $d< d_0(n)-1$.<br />Edited 04/05/17 to add a new reference

Details

Database :
OpenAIRE
Accession number :
edsair.doi...........522569ca77a0ddeae1072b21daf0aa73
Full Text :
https://doi.org/10.48550/arxiv.1608.05741