Оценка диаметра графа

[alcoholist]

Помогите старику, всё забыл, а не гуглится.
Где можно посмотреть оценки (сверху) диаметра связного графа через наименьшую степень вершин и их количество?

[Sender]

Пусть имеется граф $G$ с количеством вершин $n$, степень каждой из которых не менее $\delta$, а диаметр графа равен $D$.
Возьмём какую-нибудь вершину $A$ и обозначим $c(r)$ количество вершин графа $G$, расстояние от каждой из которых до $A$ составляет ровно $r$. Рассмотрим вершины, расстояние от которых до $A$ равно $r$, где $0 < r < D$. Обозначим их множество $S_r$. В соответствии с ранее введёнными обозначениями $|S_r|=c(r)$. Каждая вершина из $S_r$ может быть смежна только с вершинами из $S_r$, $S_{r-1}$ и $S_{r+1}$, исключая её саму.
Таким образом, $c(r)+c(r-1)+c(r+1)-1 \geqslant \delta$.
Запишем $D-1$ таких неравенств для всех $r$ от $1$ до $D-1$:
$c(0)+c(1)+c(2)-1 \geqslant \delta$
$c(1)+c(2)+c(3)-1 \geqslant \delta$

$\cdots$

$c(D-2)+c(D-1)+c(D)-1 \geqslant \delta$
Просуммируем их с учётом того, что $\sum\limits_{r=0}^Dc(r)=n$:
$3n-2(c(0)+c(D))-(c(1)+c(D-1))-(D-1) \geqslant (D-1) \delta$
$c(0)=1$ (Это наша вершина $A$). $c(D)$ при $D>1$ тоже можно сделать равным $1$ без уменьшения диаметра графа - просто перенесём лишние вершины в середину графа, соединив их, к примеру, со всеми вершинами из $S_1$. Точно так же при необходимости мы можем уменьшить $c(1)$ и $c(D-1)$ до $\delta$ при $D>3$.
Тогда
$3n-4-2\delta \geqslant (D-1)(\delta+1)$
$D \leqslant 1+\frac{3n-4-2\delta }{\delta+1}$
Эту оценку можно незначительно улучшить, если увидеть, что $c(0)+c(1)+c(2) \geqslant \delta+2$ ($c(0)=1$, $c(1) \geqslant \delta$, $c(2) \geqslant 1$), аналогично
$c(1)+c(2)+c(3) \geqslant \delta+2,$
$c(D-3)+c(D-2)+c(D-1) \geqslant \delta+2,$
$c(D-2)+c(D-1)+c(D) \geqslant \delta+2.$
Тогда

$$D \leqslant 3\frac{n-2}{\delta+1}-1 \eqno{(1)}$$

Эта оценка достигается на некоторых графах. Рассмотрим такой граф диаметра $D=3k-1$, $k>1$, что

$$c(r)= \left\{\begin{matrix} \delta-1, r \equiv 1(\mod 3) \wedge r \notin \{1,D-1\}, \\ \delta, \; \; \; r \in \{1,D-1\}, \\ 1, r \not\equiv 1(\mod 3) \wedge r \notin \{1,D-1\}, \end{matrix}\right.$$

где при всех $r$ все вершины из $S_r$ соединены между собой, со всеми вершинами из $S_{r-1}$, если $r>0$, и со всеми вершинами из $S_{r+1}$, если $r<D$. Очевидно, степень каждой вершины такого графа не менее $\delta$, а общее количество его вершин составит $n=k(\delta+1)+2,$ что в точности соответствует оценке $(1)$.

[sqribner48]

alcoholist
У меня есть статья Wayne Goddard and Ortrud R. Oellermann «Distance in Graphs», непонятно где напечатанная, может это отрывок из книги или из лекции. Там есть много чего о диаметре.
Если укажете эл. адрес куда ее послать то вышлю по эл. почте.
Пока привожу отрывок из статьи, может вам пригодится.

Цитата:

We look next at upper bounds involving the minimum or maximum degree.
Theorem 1. For a graph $G$ of order $n$:
1. $diam(G) \leqslant (n - \Delta(G) + 1)$.
2. [71] $rad(G) \leqslant (n - \Delta(G))/2 + 1$.
3. If $\delta(G) \geqslant n/2$, then $diam(G) \leqslant 2$.
and these bounds are sharp.

(Оффтоп)

P.S. Что-то рано Вы себя в старики записали

[Sender]

Перечитал свои рассуждения, всё-таки обозначать всё на свете одной буквой было не лучшей идеей. Поправил.