Anti-directed 2-factor conjecture for dense directed graphs

About 16 years old · traced to

Let DD be a directed graph of even order n≥8n \geq 8, and let δ(D)\delta(D) denote its minimum total degree. An anti-directed 2-factor is a spanning 2-regular subgraph whose cycle edges, viewed as arcs of DD, alternate in direction along each cycle.

Anti-directed 2-factor conjecture. If

δ(D)≥12n,\delta(D) \geq \frac{1}{2}n,

then DD contains an anti-directed 2-factor.

This conjecture is motivated by the paper's δ(D)>2446n\delta(D)>\frac{24}{46}n sufficient condition and by examples showing that the threshold cannot be lowered in general. The source does not state whether the conjecture has been resolved.

References

Primary source

Ajit A. Diwan, Josh B. Frye, Michael J. Plantholt and Shailesh K. Tipnis, “A sufficient condition for the existence of an anti-directed 2-factor in a directed graph”, arXiv:1012.1231 (2011).

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.