RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2002 Volume 14, Issue 2, Pages 119–133 (Mi dm246)

Dichotomous graphs whose girth is one less than the maximum

A. V. Knyazev


Abstract: 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.

UDC: 519.15

Received: 18.03.2002

DOI: 10.4213/dm246


 English version:
Discrete Mathematics and Applications, 2002, 12:3, 303–318

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025