Dichotomous graphs whose girth is one less than the maximum

A. V. Knyazev

Diskretnaya Matematika, Tome 14 (2002) no. 2, pp. 119-133

Résumé

We say that a digraph is 2-regular (dichotomous) if the out-degrees $d_0(j)$ and in-degrees $d_1(j)$ of any its vertex $j\in V$ satisfy the equality $d_0(j)=d_1(j)=2$. A graph $\Gamma$ is said to be primitive if for any pair $i$ and $j$ of its vertices in $\Gamma$ there exists a path from $i$ to $j$ of length $m>0$. The least $m$ is denoted $\gamma(\Gamma)$ and called the exponent of $\Gamma$. Let $G(n,2,p)$ stand for the class of strongly connected 2-regular graphs with $n$ vertices of girth (the length of the shortest circuit) $p$, and let $P(n,2,p)$ denote the class of primitive 2-regular graphs of girth $p$ with $n$ vertices. The girth of a 2-regular graph with $n$ vertices does not exceed $]n/2[$, where $]x[$ is the least integer no smaller than $x$. Earlier, the author proved that any primitive 2-regular graph with $n$ vertices and with the maximal possible girth $]n/2[$ had the exponent equal exactly to $n-1$. In this paper we prove that for odd $n\ge 13$ $$ G(n,2,(n-1)/2)=P(n,2,(n-1)/2), $$ any graph in $G(n,2,(n-1)/2)$ has a circuit of length $(n+1)/2$, and for any $\Gamma\in G(n,2,(n-1)/2)$ the inequality $$ \gamma(\Gamma)\le \frac{(n-1)^2}4+5 $$ is true.