Restrictions on girths in compact graphs.pdf Условие компактности [1] регулярного графа коррелирует его порядок n со степе-нью s и минимально возможным диаметром d:1 + s Е (s - 1)j - 1 < n ^ 1 + s Е (s - j=1 j=1 1)j - 1.Заметим, что область определения порядка компактных графов с заданными значени-ями степени и диаметра является в данном выражении максимальной и предполагаетналичие в них всего спектра k циклов от k = 3 до максимально возможного значенияk = 2d + 1 , при этом значения обхвата g, равные длине минимального цикла в графе,определены соответствующей областью 3 < g ^ 2d + 1.Перепишем (для случая s > 2) условие в видеs(s - 1)d-1 - 2 s(s - 1)d - 2- < n ^ - .s - 2 s - 2Пусть регулярный граф G( V, E) порядка n и степени s n(s)-компактен: его диаметрd > 1 и значения n и s соответствуют данному выше условию компактности (слу-чай с d =1 для s-регулярного графа соответствует полному графу, обхват которогоg(G) = 3). Кратность вершин в рассматриваемых проекциях простых графов проявля-ется только на уровнях выше первого - в противном случае это были бы мультиграфы,находящиеся вне нашего рассмотрения. Основанная на проективном описании возмож-ность синтеза регулярных графов с заданными значениями порядка, степени и обхватавпервые представлена в [2]. Там же показано, что наличие в проекции графа однойили нескольких кратных вершин означает наличие в графе цикла длины k, равнойсумме номеров уровней, на которых расположены эта или эти вершины; например,если вершина u G V входит в состав проекции дважды, т. е. ее кратность mu равна 2,и входит она в состав подмножества вершин одного уровня или двух подмножествразных уровней u G Vj, u G Vj проекции, то этой проекцией определен цикл длиныk = i + j, i , j G (1, 2,...,d).Отметим, что случай n = Nd(s) = (s(s - 1)d - 2) /(s - 2) соответствует П^)-ком-пактному графу с максимально возможным обхватом g(G) = 2d + 1 (если такой графсуществует) и отсутствию в любой из его проекций вплоть до d-уровня кратных вер-шин. Кратными в проекции Pd(v) называем перечисленные в ней повторяющиеся вер-шины. Попытка синтезировать граф с меньшим, чем 2d +1, обхватом приведет к по-явлению кратных вершин на уровнях i < d, по крайней мере, в тех его проекци-ях, ракурсные вершины которых входят в циклы соответствующей длины. При этомd-уровневые проекции с кратными вершинами теряют вершинную полноту, что уве-личивает эксцентриситеты этих ракурсных вершин, а следовательно, и диаметр гра-фа, т. е. граф теряет свойство компактности. Таким образом, n(s)-компактных графовс n = Nd(s) и обхватом g(G) < 2d +1 не существует, иначе говоря, при генерацииn(s)-компактного графа с n = Nd(s) все k-циклы длины k < 2d +1 должны бытьзапрещены, т. е. из всех потенциальных подмножеств [2] вершин любого i-го (i ^ d)уровня каждой d-уровневой проекции синтезируемого графа должны быть изъятывершины, уже вошедшие в состав j-х уровней, j ^ i.Приведенное выше условие компактности графов является обобщенным и допуска-ет наличие в них k-циклов любой длины, 3 ^ k ^ 2d +1. В [1, 2] показаны возможностигенерации лимитируемых обхватом n^-компактных графов. В данной работе полу-чены аналитические условия существования таких графов.Рассмотрим, каким образом изменятся граничные значения числа вершин n(s)-компактного графа при наличии в нем хотя бы одного 3-цикла, что соответствуетграфу с обхватом g = 3. Наличие всего одного 3-цикла в регулярном графе вызоветнеизбежное появление на втором уровне каждой из трёх его проекций, ракурсные вер-шины которых образуют этот 3-цикл, двух вершин, кратных двум вершинам первогоуровня. Таким образом, максимально возможное число некратных вершин второгоуровня уменьшается на две; каждая кратная вершина i-го уровня (1 < i ^ d) вызыва-ет масштабируемое множителем s - 1 уменьшение числа некратных вершин на (i + 1)-муровне. Доказано, что порожденные кратными вершинами вершины также являютсякратными. В соответствии с этим число md(3) кратных вершин на всех d уровняхкомпактного графа, обусловленное наличием в нем всего одного 3-цикла, составитТогда для того, чтобы граф порядка n оставался компактным, несмотря на нали-чие в нем одного 3-цикла, должно быть выполнено условие n + md (3) ^ Nd (s), т.е.n ^ Nd (s) - md (3), илиd-1md(3) = 2 + 2 (s - 1) + ... + 2(s - 1)d-1 = 2 . (s - 1)j -1i=1 s 2Если же( i\d-1/ , i\ ^ / s ( s - 1) ( s - 1) (s + 1 ) < n ^ - - 2 ,то граф теряет свойство компактности при наличии в нем хотя бы одного треугольногоцикла. Иными словами, при генерации n(s)-компактного графа, удовлетворяющегоприведенному выше условию, из всех потенциальных подмножеств вершин второгоуровня любой из проекций графа необходимо исключить все вершины первого уровняэтой проекции.Получены аналогичные формулы для любых k-циклов, 3 < k ^ 2d - 1.

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