A note on minimal directed graphs with given girth
type: Item
instance of: scholarly article
title: A note on minimal directed graphs with given girth
zbMATH Open document ID: 0643.05036
DOI: 10.1016/0095-8956(87)90009-8
author: Yahya Ould Hamidoune
published in: Journal of Combinatorial Theory. Series B
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4047758
zbMATH Keywords: Caccetta/Häggkvist conjecture
zbMATH Keywords: directed graph
zbMATH Keywords: girth
zbMATH Keywords: circuit
MaRDI profile type: Publication
full work available at URL: 0095-8956(87)90009-8
OpenAlex ID: W2165664494
cites work: On minimal regular digraphs with given girth
cites work: Minimal 2-regular digraphs with given girth
cites work: Q5615282
cites work: Q4078059
cites work: Q4192089
cites work: A note on the girth of digraphs
cites work: An application of connectivity theory in graphs to factorizations of elements in groups
description: scientific article; zbMATH DE number 4047758