A note on minimal directed graphs with given girth
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.
- On the girth of digraphs
- scientific article; zbMATH DE number 2188339
- On the Caccetta-Häggkvist conjecture
- Proof of the Caccetta-Häggkvist conjecture for oriented graphs with positive minimum out-degree and of independence number two
- Counting subgraphs: A new approach to the Caccetta-Häggkvist conjecture
- A note on the girth of digraphs
- An application of connectivity theory in graphs to factorizations of elements in groups
- scientific article; zbMATH DE number 3496201 (Why is no real title available?)
- scientific article; zbMATH DE number 3630786 (Why is no real title available?)
- scientific article; zbMATH DE number 3338381 (Why is no real title available?)
- Minimal 2-regular digraphs with given girth
- On minimal regular digraphs with given girth
- A note on graphs with large girth and small minus domination number
- Counting subgraphs: A new approach to the Caccetta-Häggkvist conjecture
- Some approaches to a conjecture on short cycles in digraphs
- Minimum order of loop networks of given degree and girth
- Total domination and the Caccetta-Häggkvist conjecture
- Mixed cages
- Yahya Ould Hamidoune's mathematical journey: a critical review of his work
- On the Caccetta-Häggkvist conjecture with forbidden subgraphs
- scientific article; zbMATH DE number 3861195 (Why is no real title available?)
- A note on minimum graphs with girth pair (4, 2l + 1)
- On the Caccetta-Häggkvist conjecture with a forbidden transitive tournament
- Short rainbow cycles in graphs and matroids
- Rainbow cycles for families of matchings
- Degree conditions forcing oriented cycles
- Notes on Aharoni's rainbow cycle conjecture
- Bounds on the acyclic disconnection of a digraph
- Short rainbow cycles for families of matchings and triangles
- The Hoàng-Reed conjecture for \(\delta ^{+}=3\)
This page was built for publication: A note on minimal directed graphs with given girth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1101462)
