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