A note on minimal directed graphs with given girth (Q1101462): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0095-8956(87)90009-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2165664494 / rank | |||
Normal rank |
Revision as of 22:28, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on minimal directed graphs with given girth |
scientific article |
Statements
A note on minimal directed graphs with given girth (English)
0 references
1987
0 references
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.
0 references
Caccetta/Häggkvist conjecture
0 references
directed graph
0 references
girth
0 references
circuit
0 references