A note on minimal directed graphs with given girth (Q1101462): Difference between revisions

The paper deals with the minimum order n of a directed graph \(G=(V,E)\) with given minimum outdegree at least r and girth g. The girth g is defined to be the minimum length of a circuit in G having at least one circuit. Caccetta and Häggkvist conjectured that \(n\geq r(g-1)+1\) and gave a proof for \(r=2\). The author proves this conjecture for \(r=3\). He makes use of a result of Bermond saying that if for a directed graph G with girth g and order n for every vertex x of \(Gd^+(x)\geq 3\) and \(d^-(x)\geq 3\), then \(n\geq 3g-2\). By trying to construct a counterexample of minimal cardinality which leads to a contradiction, it is then shown that already for a directed graph G with girth g and \(d^+(x)=3\) the relation \(n\geq 3g-2\) holds.