A note on minimal directed graphs with given girth (Q1101462): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: On minimal regular digraphs with given girth / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimal 2-regular digraphs with given girth / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5615282 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4078059 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4192089 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on the girth of digraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An application of connectivity theory in graphs to factorizations of elements in groups / rank | |||
Normal rank |
Latest revision as of 16:58, 18 June 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