|
This article is cited in 9 scientific papers (total in 9 papers)
Applied Graph Theory
The new universal estimation for exponents of graphs
V. M. Fomichevabc a Financial University under the Government of the Russian Federation, Moscow, Russia
b National Research Nuclear University MEPhI (Moscow Engineering Physics Institute), Moscow, Russia
c The Institute of Informatics Problems of the Russian Academy of Sciences, Moscow, Russia
Abstract:
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.
Citation:
V. M. Fomichev, “The new universal estimation for exponents of graphs”, Prikl. Diskr. Mat., 2016, no. 3(33), 78–84
Linking options:
https://www.mathnet.ru/eng/pdm551 https://www.mathnet.ru/eng/pdm/y2016/i3/p78
|
Statistics & downloads: |
Abstract page: | 271 | Full-text PDF : | 87 | References: | 37 |
|