The improvement of exponent's estimates for primitive graphs
Prikladnaâ diskretnaâ matematika, no. 13 (2011), pp. 98-100
Citer cet article
Voir la notice de l'article provenant de la source Math-Net.Ru
The estimates of exponents of $n$-vertex primitive digraphs are improved. The digraphs considered contain two prime contours whose lengths $l$ and $\lambda$ are coprime numbers. Accessible estimates of the order $O(\max\{l\lambda,f(l,\lambda,n)\})$ are obtained, where $f(l,\lambda,n)$ is a linear polynomial. Primitive digraphs whose exponents are maximal ($n^2-2n+2$, H. Wielandt, 1950), are described completely. The estimates of exponents of $n$-vertex primitive undirected graphs are improved too. In particular, the exponent of an undirected graph is no more $2n-l-1$ where $l$ is the length of the longest cycle with odd length in graph. Primitive undirected graphs whose exponents are maximal ($2n-2$) are described completely.
[2] Birkgof G., Teoriya reshëtok, Nauka, M., 1984
[3] Sachkov V. N., Tarakanov V. E., Kombinatorika neotritsatelnykh matrits, TVP, M., 2000 | Zbl
[4] Wielandt H., “Unzerlegbare nicht negative Matrizen”, Math. Zeitschr., 52 (1950), 642–648 | DOI | MR | Zbl
[5] Fomichëv V. M., “Otsenki eksponentov primitivnykh grafov”, Prikladnaya diskretnaya matematika, 2011, no. 2, 101–112