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/}
}
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/