On a problem of Lewin
type: Item
instance of: scholarly article
title: On a problem of Lewin
zbMATH Open document ID: 0901.05049
DOI: 10.1016/S0024-3795(97)00389-3
author: J. Shen
author: Stewart W. Neufeld
published in: Linear Algebra and its Applications
publication date: 1998-12-02T00:00:00Z
review text: A digraph is said to be primitive if for some positive integer \(k\) there is a walk of length exactly \(k\) from each vertex \(u\) to each vertex \(v\), possibly \(u\) again. In a primitive digraph \(G\), the smallest such \(k\) is called the exponent of \(G\), denoted by \(\exp(G)\). The parameter \(j(G)\) is the smallest \(k\) for which there is both a walk of length \(k\) and a walk of length \(k+1\) from some vertex \(u\) to some vertex \(v\), possibly \(u\) again. Then \(j(G)\leq\exp(G)\). By a theorem of Wielandt, we have \(j(G)\leq n^2- 2n+2\). The present paper gives finer upper bounds on \(j(G)\) as well as an open problem.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1154669
zbMATH Keywords: primitive digraph
reviewed by: Wai-Kai Chen
MaRDI profile type: Publication
cites work: On exponents of primitive matrices
cites work: A system of gaps in the exponent set of primitive matrices
cites work: Exponents of indecomposability
cites work: Unzerlegbare, nicht negative Matrizen
Wikidata QID: Q126388748
description: scientific article; zbMATH DE number 1154669