Асимптотическое приближение числа n-вершинных графов заданного диаметра
Доказано, что при фиксированном к ^ 3 асимптотически равномощны следующие классы помеченных n-вершинных графов: графы диаметра к, связные графы диаметра не менее к и графы (не обязательно связные), имеющие кратчайшую цепь длины не менее к. Получено асимптотически точное приближение числа таких n-вершинных графов, и найдена явная оценка погрешности при этом приближении. Тем самым улучшены оценки для асимптотического приближения числа n-вершинных графов фиксированного диаметра к, которое ранее получили Фюреди и Ким. Установлено, что почти все графы диаметра к имеют единственную пару диаметральных вершин, но почти все графы диаметра 2 имеют более одной пары таких вершин