On the girth of digraphs

DOI10.1016/S0012-365X(99)00323-4MaRDI QIDQ1969785zbMATH OpenOpenAlexFDO

Authors J. Shen

Publication date 8 October 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)00323-4

zbMATH Keywords

diameterdigraphgirthminimum out-degree

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Review text

Let \(G\) denote a strongly-connected digraph with \(n\) nodes, girth \(g\), and diameter \(D\). The author shows that if \(G\) has \(t\) nodes of out-degree one, then \(D\leq n-g+ t\). He also shows that if \(r\) denotes the minimum out-degree of \(G\), then \(g\leq \max\{\lceil n/r\rceil, 2r- 2\}\). This last result implies that when \(n\geq 2r^2- 3r+ 1\), then the conjecture of \textit{L. Caccetta} and \textit{R. Häggkvist} [Proc. 9th Southeast Conference on Combinatorics, graph theory and computing, Boca Raton 1978, 181-187 (1978; Zbl 0406.05033)] holds, namely, that \(g\leq \lceil n/r\rceil\).

Recommendations

• Digraph girth via chromatic number
• The digrundy number of digraphs
• DAG-width and circumference of digraphs
• scientific article; zbMATH DE number 4019096
• Digraphs of bounded width
• scientific article; zbMATH DE number 969185
• scientific article; zbMATH DE number 568850
• scientific article; zbMATH DE number 4055643
• scientific article; zbMATH DE number 2188339
• Distance and size in digraphs

Cited in

(26)

• Note on the regular digraphs
• A note on minimal directed graphs with given girth
• Graphs and digraphs with given girth and connectivity
• Species on digraphs
• A proof of Jean de Rumeur's conjecture
• Short cycles in digraphs with local average outdegree at least two
• Minimum order of loop networks of given degree and girth
• Total domination and the Caccetta-Häggkvist conjecture
• On diregular digraphs with degree two and excess three
• Oriented bipartite graphs and the Goldbach graph
• On the parameterized complexity of 2-partitions
• Short directed cycles in bipartite digraphs
• Short cycles in oriented graphs
• On the Caccetta-Häggkvist conjecture with forbidden subgraphs
• The surviving rate of digraphs
• On the Caccetta-Häggkvist conjecture with a forbidden transitive tournament
• A sufficient condition for digraphs with girth at most 4
• On Iterated Image Size for Point-Symmetric Relations
• scientific article; zbMATH DE number 2230268 (Why is no real title available?)
• Rainbow cycles for families of matchings
• Nonuniform Degrees and Rainbow Versions of the Caccetta–Häggkvist Conjecture
• Degree conditions forcing oriented cycles
• Short rainbow cycles for families of matchings and triangles
• Short rainbow cycles for families of small edge sets
• Aharoni's rainbow cycle conjecture holds up to an additive constant
• Cycles of given length in oriented graphs

This page was built for publication: On the girth of digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1969785)