On the number of arcs in primitive digraphs with large exponents
From MaRDI portal
(Redirected from On the number of arcs in primitive digraphs with large exponents)
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\).
Recommendations
Cites work
- A system of gaps in the exponent set of primitive matrices
- Digraphs with large exponent
- Gaps in the exponent set of primitive matrices
- scientific article; zbMATH DE number 51878 (Why is no real title available?)
- On a conjecture about the exponent set of primitive matrices
- On a Problem of Partitions
- On Lewin and Vitek's conjecture about the exponent set of primitive matrices
- The Theory of Round Robin Tournaments
Cited in
(8)- The exponent of Cartesian product of cycles
- The extremal sizes of arc-maximal \((k, \ell)\)-digraphs
- k-primitivity of digraphs
- Primitive digraphs with smallest large exponent
- Nonnegative primitive matrices with exponent 2
- The vertex exponent of primitive digraph of order n with girth r
- scientific article; zbMATH DE number 1156640 (Why is no real title available?)
- Primitive graphs with given exponents and minimum number of edges
This page was built for publication: On the number of arcs in primitive digraphs with large exponents
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1870076)