An improved formula for the universal estimation of digraph exponents

V. M. Fomichev

Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 16-20

Résumé

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

Détail

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