The estimates of exponents for primitive graphs
Prikladnaâ diskretnaâ matematika, no. 2 (2011), pp. 101-112
Voir la notice de l'article provenant de 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},
publisher = {mathdoc},
number = {2},
year = {2011},
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/