Центр и его спектр почти всех n-вершинных графов заданного диаметра
Ключевые слова:
граф, диаметр, диаметральные вершины, радиус, центральные вершины, центр, спектр центра, типичные графы, почти все графы.Аннотация
Изучаются типичные (справедливые для почти всех графов рассматриваемого класса) свойства центра и его спектр (множество мощностей центров) для n-вершинных графов фиксированного диаметра k. Найден спектр центра всех и почти всех n-вершинных связных графов. Установлена структура центра почти всех n-вершинных графов заданного диаметра k. При k=1,2 любая вершина является центральной, а для $k\geq 3$ выделено два типа центральных вершин, необходимых и достаточных для получения центров почти всех таких графов, при этом для построенных типичных графов центр найден явно. Доказано, что центр почти всех n-вершинных графов диаметра k имеет мощность n-2 при k=3, а для $k\geq 4$ спектр центра ограничен интервалом из последовательных целых чисел, за исключением не более одного значения (двух значений) вне этого интервала для чётного диаметра k (для нечётного диаметра k) в зависимости от k. Для значений мощности центра вне этого интервала вычислены асимптотические доли числа графов с таким центром. Установлена реализуемость найденного спектра мощностей в качестве спектра центра типичных n-вершинных графов диаметра k.
