Bang-Jensen–Gutin–Li hamiltonicity conjecture for dominating pairs

Let DD be a finite strong digraph without loops or multiple arcs on nn vertices. For distinct vertices x,yx,y, write xyx\rightarrow y when there is an arc from xx to yy. A pair of vertices is dominating if both vertices send an arc to a common vertex, and a pair is dominated if a common vertex sends an arc to both of them. Here d(x)d(x) denotes the degree of xx.

Bang-Jensen–Gutin–Li conjecture. If

d(x)+d(y)2n1d(x)+d(y)\geq 2n-1

for every pair of dominating non-adjacent vertices and every pair of dominated non-adjacent vertices {x,y}\{x,y\}, then DD is hamiltonian.

This conjecture was raised by Bang-Jensen, Gutin and Li as a degree-sum condition combining local domination structure with hamiltonicity. It is still open and seems quite difficult.

Sources & referencesView supporting material

Primary source

Ruixia Wang, “A sufficient condition for a balanced bipartite digraph to be hamiltonian”, arXiv:1506.07949 (2017).

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.