Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It is known that every $r$-regular graph on $2r+1$ vertices is Hamiltonian (Nash-Williams theorem, see here).

Now, I wonder if there is a simpler way to show that the graph on $4n+3$ ($n \ge 1$) vertices with degree sequence $(2n+1, \ldots, 2n+1, 2n+2)$ is Hamiltonian?

("a simpler way" means not to use the arguments in the proof of Nash-Williams theorem here).

For example, the graph with degree sequence $(3, 3, 3, 3, 3, 3, 4)$ must be Hamiltonian.

share|improve this question
    
I do not know if there exist such result after the Nash-Williams theorem, but we can conclude the following corollary: Suppose $G$ is a graph on $n$ vertices with degree of each vertex is either $\left\lfloor \frac{n}{2}\right\rfloor $ or $\left\lceil\frac{n}{2}\right\rceil $. Then $G$ is Hamiltonian. –  pipi Oct 24 '12 at 4:30
    
Actually we were wondering about the same question. Have you found such a result in literature? Nash-Williams arguments seem to work, but are there any published results with or without using this argument? –  Sibel Aug 26 at 10:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.