|
О дихотомических графах с обхватом, на единицу меньшим максимального
А. В. Князев
Аннотация:
Дихотомическим называется орграф, для полустепеней исхода $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.
$$
Статья поступила: 18.03.2002
Образец цитирования:
А. В. Князев, “О дихотомических графах с обхватом, на единицу меньшим максимального”, Дискрет. матем., 14:2 (2002), 119–133; Discrete Math. Appl., 12:3 (2002), 303–318
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm246https://doi.org/10.4213/dm246 https://www.mathnet.ru/rus/dm/v14/i2/p119
|
Статистика просмотров: |
Страница аннотации: | 549 | PDF полного текста: | 228 | Список литературы: | 78 | Первая страница: | 2 |
|