Geodesic
On improved universal estimation of exponents of~digraphs
Prikladnaâ diskretnaâ matematika, no. 1 (2019), pp. 115-123.

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

An improved formula for universal estimation of exponent is obtained for $n$-vertex primitive digraphs. A previous formula by A. L. Dulmage and N. S. Mendelsohn (1964) is based on a system $\hat{C}$ of directed circuits $C_1,\ldots,C_m$, which are held in a graph and have lengths $l_1,\ldots,l_m$ with $\gcd(l_1,\ldots,l_m)=1$. A new formula is based on a similar circuit system $\hat{C}$, where $\gcd(l_1,\ldots,l_m)=d\geq 1$. Also, the new formula uses $r_{i,j}^{s/d}(\hat{C})$, that is the length of the shortest path from $i$ to $j$ going through the circuit system $\hat{C}$ and having the length which is comparable to $s$ modulo $d$, $s=0,\ldots,d-1$. It is shown, that $\text{exp}\,\Gamma\leq 1+\hat{F}(L(\hat{C}))+R(\hat{C})$, where $\hat{F}(L)=d\cdot F(l_1/d,\ldots, l_m/d)$ and $F(a_1,\ldots,a_m)$ is the Frobenius number, $R(\hat{C})=\max_{(i,j)}\max_s\{r_{i,j}^{s/d}(\hat{C})\}$. For some class of $2k$-vertex primitive digraphs, it is proved, that the improved formula gives the value of estimation $2k$, and the previous formula gives the value of estimation $3k-2$.
Keywords: the Frobenius number, primitive graph, exponent of graph. 
@article{PDM_2019_1_a7,
     author = {V. M. Fomichev},
     title = {On improved universal estimation of exponents of~digraphs},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {115--123},
     publisher = {mathdoc},
     number = {1},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_1_a7/}
}
TY  - JOUR
AU  - V. M. Fomichev
TI  - On improved universal estimation of exponents of~digraphs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 115
EP  - 123
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_1_a7/
LA  - ru
ID  - PDM_2019_1_a7
ER  - 
%0 Journal Article
%A V. M. Fomichev
%T On improved universal estimation of exponents of~digraphs
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 115-123
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2019_1_a7/
%G ru
%F PDM_2019_1_a7
V. M. Fomichev. On improved universal estimation of exponents of~digraphs. Prikladnaâ diskretnaâ matematika, no. 1 (2019), pp. 115-123. http://geodesic.mathdoc.fr/item/PDM_2019_1_a7/

[1] Frobenius F. G., “Über Matrizen aus nicht negativen Elementen”, Sitzungsber K. Preuss. Akad. Wiss., 1912, 456–477 | Zbl

[2] Dulmage A. L., Mendelsohn N. S., “Gaps in the exponent set of primitive matrices”, Illinoise J. Math., 1964, no. 8, 642–656 | DOI | MR | Zbl

[3] Fomichev V. M., Avezova Y. E., Koreneva A. M., Kyazhin S. N., “Primitivity and local primitivity of digraphs and non-Negative matrices”, Diskretnyy Analiz i Issledovanie Operatsiy, 25:3 (2018), 95–125 (in Russian) | Zbl

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

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

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

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

[8] Fomichev V. M., “Computational complexity of the original and extended Diophantine Frobenius problem”, Diskretnyy Analiz i Issledovanie Operatsiy, 24:3 (2017), 104–124 (in Russian) | Zbl

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

[10] Fomichev V. M., Mel'nikov D. A., Cryptographic Methods of Information Security, v. 1, Mathematical Aspects, YuRAYT Publ., M., 2016, 209 pp. (in Russian)

[11] Fomichev V. M., “The new universal estimation for exponents of graphs”, Prikladnaya Diskretnaya Matematika, 2016, no. 3(33), 78–84 (in Russian)