# zbMATH — the first resource for mathematics

The minimum degree approach for Paul Seymour’s distance 2 conjecture. (English) Zbl 0996.05042
Let $$D$$ be a digraph without loops and multiple edges. Let $$d_+(v)$$ be the number of vertices with out-distance one from $$v$$ and $$d_{++}(v)$$ the number of vertices with out-distance one or two from $$v$$. Seymour’s distance two conjecture is that there exists a vertex $$v$$ of $$D$$ such that $$d_{++}(v)\geq d_+(v)$$. The authors prove that this conjecture is true for minimum degree.

##### MSC:
 05C12 Distance in graphs 05C20 Directed graphs (digraphs), tournaments
##### Keywords:
digraph; distance two conjecture