Nash-Williams' directed degree-sequence conjecture

About 16 years old · traced to

Let DD be a strongly connected digraph on nn vertices, with nondecreasing out-degree sequence d1+≤⋯≤dn+d_1^+\leq\cdots\leq d_n^+ and in-degree sequence d1−≤⋯≤dn−d_1^-\leq\cdots\leq d_n^-. Nash-Williams' directed degree-sequence conjecture. If, for every integer i<n/2i<n/2, either di+≥i+1d_i^+\geq i+1 or dn−i−≥n−id_{n-i}^-\geq n-i, and either di−≥i+1d_i^-\geq i+1 or dn−i+≥n−id_{n-i}^+\geq n-i, then DD contains a Hamilton cycle. This is the proposed directed analogue of Chvátal's theorem; the source describes the asymptotic version as a consequence of its results, while the exact conjecture is not resolved here.

References

Primary source

Zhilan Wang and Jin Yan, “The H-linkage problems in sparse robustly expanding digraphs”, arXiv:2604.27452 (2026).

Additional references

2 papers in this index state this conjecture (2010–2026). The statement above is taken from the most recent of them; the others are arXiv:1006.0590.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.