Bounds of the longest directed cycle length for minimal strong digraphs
type: Item
instance of: scholarly article
title: Bounds of the longest directed cycle length for minimal strong digraphs
zbMATH Open document ID: 0651.05045
DOI: 10.1016/0012-365X(88)90037-4
author: Zhibo Chen
author: Fuji Zhang
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: The subjects of the paper are directed cycles in minimal strong digraphs. A digraph D is called strong if it contains a directed (u,v)-path for any ordered set of vertices (u,v). If D is strong and D-e is no longer strong for any arc e in D, it is called a minimal strong digraph. Let \(\nu\) (D) denote the cyclomatic number of D. First it is shown that a minimal strong digraph D has \(\nu\) (D) directed cycles such that every arc of D is contained in at least one of them. A reducible chain is defined to be a directed path \(w=(x,v_ 1,...,v_ k,y)\), \(k\geq 1\) in a strong digraph D where both indegree and outdegree of each vertex \(v_ i\) are equal to one and \(D-\{v_ 1,...,v_ k\}\) remains to be strong. The authors prove that any minimal strong digraph D with cyclomatic number \(\nu\) (D)\(\geq 2\) has at least two reducible chains. Futhermore, if C is a longest directed cycle of D, D has a reducible chain w which is arc-disjoint with C. Using these results the main theorem of the paper is proved. It gives the following sharp lower and upper bounds on length \(\ell (D)\) of the longest directed cycle in a nontrivial minimal strong digraph D \(\lceil m/(m-n+1)\rceil \leq \ell (D)\leq 2n-m\), where n and m are the number of nodes and arcs in D respectively. Finally it is mentioned (without proof) that an analogous result \(\lceil 2m/(m-n+2)\rceil \leq \ell (G)\leq 2n-m\) can be derived for minimal 2-edge connected graphs G (without cut vertices).
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4061283
zbMATH Keywords: bounds on cycle lengths
zbMATH Keywords: minimal strong digraphs
zbMATH Keywords: cyclomatic number
zbMATH Keywords: reducible chain
zbMATH Keywords: longest directed cycle
MaRDI profile type: Publication
cites work: Q4099676
cites work: Chemins Et Circuits Dans Les Graphes Orientes
cites work: Cycles in digraphs– a survey
cites work: Diconnected Orientations and a Conjecture of Las Vergnas
cites work: On basis diagraphs
cites work: On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
cites work: Long Cycles in Digraphs
full work available at URL: 0012-365x(88)90037-4
OpenAlex ID: W2010123480
description: scientific article; zbMATH DE number 4061283