Anti-directed 2-factor conjecture for dense directed graphs

Let DD be a directed graph of even order n8n \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.

Sources & referencesView supporting material

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.