Name
Abstract | ||
|---|---|---|
Let n,d be integers with 1≤d≤n−12, and set h(n,d)≔n−d2+d2 and e(n,d)≔max{h(n,d),h(n,n−12)}. Because h(n,d) is quadratic in d, there exists a d0(n)=(n∕6)+O(1) such that e(n,1)>e(n,2)>⋯>e(n,d0)=e(n,d0+1)=⋯=en,n−12.A theorem by Erdős states that for d≤n−12, any n-vertex nonhamiltonian graph G with minimum degree δ(G)≥d has at most e(n,d) edges, and for d>d0(n) the unique sharpness example is simply the graph Kn−E(K⌈(n+1)∕2⌉). Erdős also presented a sharpness example Hn,d for each 1≤d≤d0(n). |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.disc.2016.08.030 | Discrete Mathematics |
Keywords | Field | DocType |
Turán problem,Hamiltonian cycles,Extremal graph theory | Integer,Discrete mathematics,Graph,Combinatorics,Mathematics | Journal |
Volume | Issue | ISSN |
340 | 11 | 0012-365X |
Citations | PageRank | References |
2 | 0.41 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zoltán Füredi | 1 | 1237 | 233.60 |
| Alexandr V. Kostochka | 2 | 682 | 89.87 |
| Ruth Luo | 3 | 8 | 2.75 |