Geodesic
An improved formula for the universal estimation of digraph exponents
Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 16-20.

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

An early formula by A. L. Dulmage and N. S. Mendelsohn (1964) for the universal estimation of $n$-vertex primitive digraph exponent is based on a system $\hat C=\{C_1,\dots,C_m\}$ of directed circuits in the graph with lengths $l_1,\dots,l_m$ respectively such that $\mathrm{gcd}(l_1,\dots,l_m)=1$. A new formula is based on a similar circuit system $\hat C$ with $\mathrm{gcd}(l_1,\dots,l_m)=d\geq1$. Also, the new formula uses the values $r_{i,j}^{s/d}(\hat C)$ that are the lengths of the shortest paths from a vertex $i$ to a vertex $j$ going through the circuit system $\hat C$ and having the length comparable to $s$ modulo $d$, $s\in\{0,\dots,d-1\}$. It's shown, that $\exp\Gamma\leq1+\hat F(L(\hat C))+R(\hat C)$ where $\hat F(L)=d\cdot F(l_1/d,\dots,l_m/d)$ and $F(a_1,\dots,a_m)$ is the Frobenius number, $R(\hat C)=\max_{(i,j)}\max_s\{r_{i,j}^{s/d}(\hat C)\}$. For a class of $2k$-vertex primitive digraphs, it is proved that the improved formula gives the value of estimation $2k$, but the early formula gives the value of estimation $3k-2$.
Keywords: Frobenius number, primitive graph, exponent of graph. 
@article{PDMA_2018_11_a4,
     author = {V. M. Fomichev},
     title = {An improved formula for the universal estimation of digraph exponents},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {16--20},
     publisher = {mathdoc},
     number = {11},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2018_11_a4/}
}
TY  - JOUR
AU  - V. M. Fomichev
TI  - An improved formula for the universal estimation of digraph exponents
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2018
SP  - 16
EP  - 20
IS  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2018_11_a4/
LA  - ru
ID  - PDMA_2018_11_a4
ER  - 
%0 Journal Article
%A V. M. Fomichev
%T An improved formula for the universal estimation of digraph exponents
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2018
%P 16-20
%N 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2018_11_a4/
%G ru
%F PDMA_2018_11_a4
V. M. Fomichev. An improved formula for the universal estimation of digraph exponents. Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 16-20. http://geodesic.mathdoc.fr/item/PDMA_2018_11_a4/

[1] Frobenius G., “Uber Matrizen aus nicht negativen Elementen”, K. Preuss. Akad. Wiss. Berlin, 1912 (1912), 456–477 | Zbl

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

[3] Perkins P., “A theorem on regular graphs”, Pacific J. Math., 2 (1961), 1529–1533 | DOI | MR

[4] Dulmage A. L., Mendelsohn N. S., “Gaps in the exponent set of primitive matrices”, Illinoise J. Math., 86 (1958), 642–656 | MR

[5] Holladay J. C., Varga R. S., “On powers of non-negative matrices”, Proc. Amer. Math. Soc., 9 (1958), 631 | DOI | MR | Zbl

[6] Fomichev V. M., “Otsenki eksponentov primitivnykh grafov”, Prikladnaya diskretnaya matematika, 2011, no. 2(12), 101–112

[7] Fomichev V. M., “O vychislitelnoi slozhnosti originalnoi i rasshirennoi diofantovoi problemy Frobeniusa”, Diskretnyi analiz i issledovanie operatsii, 24:3 (2017), 104–124 | DOI | Zbl

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

[9] Fomichev V. M., Melnikov D. A., Kriptograficheskie metody zaschity informatsii. Ch. 1. Matematicheskie aspekty, V 2 ch., Yurait, M., 2016, 209 pp.

[10] Fomichev V. M., “Novaya universalnaya otsenka eksponentov grafov”, Prikladnaya diskretnaya matematika, 2016, no. 3(33), 78–84

[11] Fomichev V. M., Kyazhin S. N., “Lokalnaya primitivnost matrits i grafov”, Diskretnyi analiz i issledovanie operatsii, 24:1 (2017), 97–119 | DOI | MR | Zbl