On improved universal estimation of exponents of~digraphs

V. M. Fomichev

Prikladnaâ diskretnaâ matematika, no. 1 (2019), pp. 115-123

Résumé

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$.

Détail

Keywords: the Frobenius number, primitive graph, exponent of graph.