On the number of arcs in primitive digraphs with large exponents

From MaRDI portal





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\).











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)