On the diversity of balls in a graph of a given diameter.pdf В работе изучается разнообразие шаров обыкновенного связного графа в асимптотике. Пусть Ti(G) - число всех различных шаров радиуса i в метрическом пространстве графа G с обычным расстоянием между вершинами, т. е. длиной кратчайшей цепи, соединяющей эти вершины. Определение 1 [1]. Вектор т(G) = (t0(G), т1 (G),..., Td(G)), где d = d(G) - диаметр графа G, называется вектором разнообразия шаров графа G. Например, вектор разнообразия шаров простой цепи длины d, как показано в [1], равен А^ = (ДО, Af,..., Af), где ( d + 1, если 0 ^ i ^ |_d/2j , Af = 6 или d ^ 1 существует единственный такой граф - 2d-вершинный цикл при d > 3 и полный граф при d ^ 1. В настоящей работе исследуется асимптотическое поведение числа графов с локальным (полным) разнообразием шаров и строение вектора разнообразия шаров графа заданного диаметра. Хорошо известен следующий результат. Теорема 1 [6]. Почти все графы являются графами диаметра 2. Более того, справедлива следующая Теорема 2 [2]. Почти все графы являются графами диаметра 2 с полным разнообразием шаров. Непосредственно из теорем 1 и 2 вытекает Теорема 3. Граф диаметра 2 является графом полного разнообразия шаров. Основным результатом работы является следующая Теорема 4. Пусть d ^ 3. Тогда в графе диаметра d число различных шаров радиуса i равно Ad для всех i ^ d/2. Следствие 1. Пусть d ^ 3 и t ^ d/2. Тогда граф диаметра d не обладает локальным t-разнообразием шаров и, в частности, не является графом полного разнообразия шаров.

Скачать электронную версию публикации