|
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.
Received: 18.03.2002
Citation:
A. V. Knyazev, “Dichotomous graphs whose girth is one less than the maximum”, Diskr. Mat., 14:2 (2002), 119–133; Discrete Math. Appl., 12:3 (2002), 303–318
Linking options:
https://www.mathnet.ru/eng/dm246https://doi.org/10.4213/dm246 https://www.mathnet.ru/eng/dm/v14/i2/p119
|
|