The estimates of exponents for primitive graphs
Prikladnaâ diskretnaâ matematika, no. 2 (2011), pp. 101-112
Cet article a éte moissonné depuis la source Math-Net.Ru
The estimates of exponents of $n$-vertex primitive digraphs and undirected graphs are improved. The digraphs considered contain two prime contours with coprime lengths $l$ and $\lambda$. For them, accessible estimates of the order $\mathrm O(\max\{l\lambda,f(l,\lambda,n)\}$ are obtained, where $f(l,\lambda,n)$ is a linear polynomial. The exponent of undirected graph is no more $2n-l-1$, where $l$ is the length of the longest cycle with odd length in graph. Primitive digraphs with maximal exponent ($n^2-2n+2$, H. Wielandt, 1950) and undirected graphs with maximal exponent ($2n-2$) are completely described.
Keywords:
graph exponent, primitive graphs.
@article{PDM_2011_2_a8,
author = {V. M. Fomichev},
title = {The estimates of exponents for primitive graphs},
journal = {Prikladna\^a diskretna\^a matematika},
pages = {101--112},
year = {2011},
number = {2},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/PDM_2011_2_a8/}
}
V. M. Fomichev. The estimates of exponents for primitive graphs. Prikladnaâ diskretnaâ matematika, no. 2 (2011), pp. 101-112. http://geodesic.mathdoc.fr/item/PDM_2011_2_a8/
[1] Birkgof G., Teoriya reshëtok, Nauka, M., 1984 | MR
[2] Sachkov V. N., Tarakanov V. E., Kombinatorika neotritsatelnykh matrits, TVP, M., 2000 | MR | Zbl
[3] Wielandt H., “Unzerlegbare nicht negative Matrizen”, Math. Zeitschr., 52 (1950), 642–648 | DOI | MR | Zbl
[4] Berzh K., Teoriya grafov i eë primenenie, IL, M., 1962