Верхние оценки экспонентов псевдосимметрических графов

Псевдосимметрическим называется орграф с множеством вершин $V=\{1,2,\dots,n\}$, для полустепеней исхода $d_0(j)$ и захода $d_i(j)$ любой вершины $j\in V$ которого выполнено равенство $d_0(j)=d_i(j)$. Если для всех $j\in V$ справедливо равенство $d_0(j)=d_i(j)=2$, то граф называется дихотомическим. Граф $\Gamma$ называется примитивным, если для любой пары его вершин $i$ и $j$ в $\Gamma$ существует путь из $i$ в $j$ длины $m>0$. Наименьшее такое $m$ обозначается $\gamma(\Gamma)$ и называется экспонентом $\Gamma$. В § 1 данной работы доказано, что для экспонента примитивного дихотомического графа $\Gamma$ с обхватом (длиной наименьшего контура) $p>2$ $\gamma(\Gamma)\leqslant\dfrac{n(p+1)}{2p-1}+p(n-2)+5$, охарактеризована достижимость этой оценки. В § 2 доказано, что экспонент примитивного псевдосимметрического графа с обхватом $p>2$, полустепени исхода и захода вершин которого не меньше $k\geqslant3$, не превосходит $\dfrac5{2(k+1)}(n+p(2n-3))$, и охарактеризована достижимость этой оценки.