Geodesic
Dichotomous graphs whose girth is one less than the maximum
Diskretnaya Matematika, Tome 14 (2002) no. 2, pp. 119-133.

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

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. 
@article{DM_2002_14_2_a10,
     author = {A. V. Knyazev},
     title = {Dichotomous graphs whose girth is one less than the maximum},
     journal = {Diskretnaya Matematika},
     pages = {119--133},
     publisher = {mathdoc},
     volume = {14},
     number = {2},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2002_14_2_a10/}
}
TY  - JOUR
AU  - A. V. Knyazev
TI  - Dichotomous graphs whose girth is one less than the maximum
JO  - Diskretnaya Matematika
PY  - 2002
SP  - 119
EP  - 133
VL  - 14
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2002_14_2_a10/
LA  - ru
ID  - DM_2002_14_2_a10
ER  - 
%0 Journal Article
%A A. V. Knyazev
%T Dichotomous graphs whose girth is one less than the maximum
%J Diskretnaya Matematika
%D 2002
%P 119-133
%V 14
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2002_14_2_a10/
%G ru
%F DM_2002_14_2_a10
A. V. Knyazev. Dichotomous graphs whose girth is one less than the maximum. Diskretnaya Matematika, Tome 14 (2002) no. 2, pp. 119-133. http://geodesic.mathdoc.fr/item/DM_2002_14_2_a10/

[1] Gantmakher F. R., Teoriya matrits, Nauka, Moskva, 1988 | MR | Zbl

[2] Knyazev A. V., “Verkhnie otsenki eksponentov psevdosimmetricheskikh grafov”, Diskretnaya matematika, 2:4 (1990), 63–71 | MR | Zbl

[3] Knyazev A. V., “Dikhotomicheskie grafy s maksimalnym obkhvatom”, Diskretnaya matematika, 2:3 (1990), 56–64 | MR | Zbl

[4] Knyazev A. V., “O diametrakh dikhotomicheskikh grafov”, Matem. zametki, 50:1 (1992), 46–55 | MR

[5] Behzad M., “Minimal 2-regular digraphs with given girth”, J. Math. Soc. Japan, 5 (1973), 1–6 | DOI | MR

[6] Shao Jia-Yu, “On the exponent of a primitive digraph”, Linear Algebra and its Appl., 64 (1985), 21–31 | DOI | MR | Zbl

[7] Sylvester J. J., “Math questions and their solutions”, Educational Times, 41 (1884), 21

[8] Vitek Y., “Bound for a linear diophantine problem of Frobenius”, J. London Math. Soc., 1975, no. 10, 79–85 | DOI | MR | Zbl