Geodesic
The new universal estimation for exponents of graphs
Prikladnaâ diskretnaâ matematika, no. 3 (2016), pp. 78-84.

Voir la notice de l'article provenant de la source Math-Net.Ru

It is shown that, for a $n$-vertex primitive digraph $\Gamma$ with a system of directed circuits $C_1,\dots,C_k$ of lengths $l_1,\dots,l_k$ respectively, $\exp\Gamma\leq n(r+1)+g(l_1,\dots,l_k)+L$, where $r$ is the number of connected components in the digraph $C_1\cup\dots\cup C_k$, $g(l_1,\dots,l_k)$ is the Frobenius's number, and $L$ is a linear combination of the lengths of some directed circuits in $\Gamma$. This estimation is mostly better than other estimations known for many cases. Some more precise expressions of it are given for some particular types of graphs. The value of the estimation varies from $\mathrm O(n)$ to $\mathrm O(n^2)$ as $n$ increases indefinitely and equals $\mathrm O(n^2)$, only if the length of the shortest directed circuit is $\mathrm O(n)$. For Wielandt's graphs, this estimation coincides with the Wielandt's one.
Keywords: Frobenius's number, primitive graph, exponent of graph. 
@article{PDM_2016_3_a5,
     author = {V. M. Fomichev},
     title = {The new universal estimation for exponents of graphs},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {78--84},
     publisher = {mathdoc},
     number = {3},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2016_3_a5/}
}
TY  - JOUR
AU  - V. M. Fomichev
TI  - The new universal estimation for exponents of graphs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2016
SP  - 78
EP  - 84
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2016_3_a5/
LA  - ru
ID  - PDM_2016_3_a5
ER  - 
%0 Journal Article
%A V. M. Fomichev
%T The new universal estimation for exponents of graphs
%J Prikladnaâ diskretnaâ matematika
%D 2016
%P 78-84
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2016_3_a5/
%G ru
%F PDM_2016_3_a5
V. M. Fomichev. The new universal estimation for exponents of graphs. Prikladnaâ diskretnaâ matematika, no. 3 (2016), pp. 78-84. http://geodesic.mathdoc.fr/item/PDM_2016_3_a5/

[1] Wielandt H., “Unzerlegbare nicht negative Matrizen”, Math. Zeitschr., 52 (1950), 642–648 | DOI | MR | Zbl

[2] Sachkov V. N., Tarakanov V. E., Combinatorics of Non-Negative Matrices, TVP Publ., Moscow, 2000 (in Russian) | MR

[3] Fomichev V. M., “The estimates of exponents for primitive graphs”, Prikladnaya Diskretnaya Matematika, 2011, no. 2(12), 101–112 (in Russian)

[4] Kogos K. G., Fomichev V. M., “Positive properties of non-negative matrices”, Prikladnaya Diskretnaya Matematika, 2012, no. 4(18), 5–13 (in Russian)

[5] Fomichev V. M., “Primitive sets of numbers being equivalent by Frobenius”, Prikladnaya Diskretnaya Matematika, 2014, no. 1(23), 20–26 (in Russian)

[6] Kyazhin S. N., Fomichev V. M., “About primitive systems of natural numbers”, Prikladnaya Diskretnaya Matematika, 2012, no. 2(16), 5–14 (in Russian)

[7] Rosser B., “The $n$-th prime is greater than $n\log n$”, Proc. London Math. Soc., 45 (1939), 21–44 | DOI | MR

[8] Alfonsin J. R., The Diophantine Frobenius Problem, Oxford University Press, 2005 | MR | Zbl

[9] Fomichev V. M., “Estimates for exponent of some graphs by Frobenius's numbers of three arguments”, Prikladnaya Diskretnaya Matematika, 2014, no. 2(24), 88–96 (in Russian)