-1
$\begingroup$

For a finite, simple undirected graph $G=(V,E)$ let $\delta(G)$ denote the minimum degree of all vertices. For any integer $k\geq 4$ let $N(k)$ denote the maximum $\delta(G)$ that a connected graph $G$ on $k$ vertices can have such that $G$ does not have a Hamiltonian path.

Do we have $\lim \sup_{k\to \infty} \frac{N(k)}{k} = 1$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

No, a graph with $\delta(G)\geqslant (k-1)/2$ has Hamiltonian path by Dirac's theorem. But for $\delta(G)=(k-2)/2$ this is already not always so, see $K_{m,m+2}$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ A minor nitpick, but $K_{m,m+1}$ does have a Hamiltonian path. $\endgroup$
    – Gordon Royle
    Commented Apr 5, 2017 at 12:27
  • $\begingroup$ Ah, path. I thought about cycle. $\endgroup$
    – Fedor Petrov
    Commented Apr 5, 2017 at 12:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .