×

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
PDF BibTeX XML Cite