On the number of arcs in primitive digraphs with large exponents
type: Item
instance of: scholarly article
title: On the number of arcs in primitive digraphs with large exponents
zbMATH Open document ID: 1017.05045
DOI: 10.1016/S0024-3795(02)00568-2
author: J. Shen
author: Cynthia J. Wyels
published in: Linear Algebra and its Applications
publication date: 2003-05-04T00:00:00Z
review text: A digraph \(G\) is primitive if there is a walk of length exactly \(k\) from each vertex \(u\) to each vertex \(v\) (possibly \(u\)) for a positive integer \(k\). The smallest such \(k\) is \(\exp(G)\). Suppose \(f(n,r)\) is the maximum number of arcs in a primitive digraph with \(n\) vertices and \(\exp(G)\geq r^2 n^2\) where \(r\) satisfies \(0< r< 1\). The authors establish the property that \(f(n,r)/n^2\) is asymptotically \((1- r)^2/3\) whenever \(r\geq \sqrt{2}/2\).
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1903589
zbMATH Keywords: walk
reviewed by: David P. Brown
MaRDI profile type: Publication
cites work: On a Problem of Partitions
cites work: Gaps in the exponent set of primitive matrices
cites work: The Theory of Round Robin Tournaments
cites work: Digraphs with large exponent
cites work: A system of gaps in the exponent set of primitive matrices
cites work: On a conjecture about the exponent set of primitive matrices
cites work: Q4002255
cites work: On Lewin and Vitek's conjecture about the exponent set of primitive matrices
description: scientific article; zbMATH DE number 1903589