О дихотомических графах с обхватом, на единицу меньшим максимального
А. В. Князев
Аннотация:
Дихотомическим называется орграф, для полустепеней исхода
$d_0(j)$ и захода
$d_1(j)$ любой вершины
$j\in V$ которого выполнено равенство
$d_0(j)=d_1(j)=2$. Граф
$\Gamma$ называется примитивным, если для любой пары его вершин
$i$ и
$j$ в
$\Gamma$ существует путь из
$i$ и
$j$ длины
$m>0$. Наименьшее такое
$m$ обозначается
$\gamma(\Gamma)$ и называется экспонентом
$\Gamma$. Обозначим через
$G(n,2,p)$ класс сильно связных дихотомических графов с
$n$ вершинами и с обхватом (длиной кратчайшего контура)
$p$, а через
$P(n,2,p)$ класс примитивных
$n$-вершинных дихотомических графов с обхватом
$p$. Обхват
$n$-вершинного дихотомического графа не превосходит
$]n/2[$, где
$]x[$ — наименьшее целое число, не меньшее
$x$. Ранее автором было доказано, что любой примитивный дихотомический
$n$-вершинный граф с максимально возможным обхватом
$]n/2[$ имеет экспонент, равный в точности
$n-1$. В настоящей работе доказано, что при нечетном
$n\ge13$
$$
G(n,2,(n-1)/2)=P(n,2,(n-1)/2),
$$
причем любой граф из
$G(n,2,(n-1)/2)$ имеет контур длины
$(n+1)/2$; для любого графа
$\Gamma$ из
$G(n,2,(n-1)/2)$ справедливо неравенство
$$
\gamma(\Gamma)\le\frac{(n-1)^2}4+5.
$$
УДК:
519.15
Статья поступила: 18.03.2002
DOI:
10.4213/dm246