О радиусе и типичных свойствах n-вершинных графов заданного диаметра

Аннотация

Свойство графов рассматриваемого класса  типичное, если почти все графы этого класса обладают данным свойством. Изучаются типичные свойства класса n-вершинных графов фиксированного диаметра k. Построено семейство вложенных классов типичных n-вершинных графов заданного диаметра $k\geq 3$, обладающих рядом метрических свойств. На основе типичных свойств метрических шаров, содержащихся в графе, установлен радиус почти всех n-вершинных графов исследуемых классов. Доказано, что для любого фиксированного $k\geq 3$ почти все n-вершинные графы диаметра k имеют радиус $\lceil \frac{k}{2} \rceil$, при этом радиус почти всех графов диаметра k=1,2 равен диаметру. Все найденные типичные свойства n-вершинных графов  фиксированного диаметра $k\geq 2$ остаются справедливыми для связных графов диаметра не менее k, а также для графов (не обязательно связных), содержащих кратчайшую цепь длины не менее k.