RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2002, том 14, выпуск 2, страницы 119–133 (Mi dm246)

О дихотомических графах с обхватом, на единицу меньшим максимального

А. В. Князев


Аннотация: Дихотомическим называется орграф, для полустепеней исхода $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


 Англоязычная версия: Discrete Mathematics and Applications, 2002, 12:3, 303–318

Реферативные базы данных:


© МИАН, 2024