About primitive regular graphs with exponent 2.pdf Неотрицательная квадратная матрица A называется примитивной, если существует натуральное k, такое, что Ak положительна. Минимальное такое значение k называется экспонентом матрицы A [1]. Понятие примитивности легко переносится на графы. Вершина v достижима из вершины u за k ^ 1 шагов, если существует последовательность рёбер (маршрут) {u,w1}, {w1, w2},... , {wk-1, v}. Если A - матрица смежности графа G, то достижимость вершины v из вершины u за k шагов означает, что на пересечении строки и столбца, соответствующих вершинам u и v соответственно, в матрице Ak стоит 1. Граф G называется примитивным, если существует натуральное k, такое, что между любой парой вершин графа G существует маршрут длины k (иначе говоря, в матрице Ak все элементы равны 1). Минимальное такое значение k называется экспонентом графа G и обозначается exp(G). Ряд работ посвящён исследованию экспонентов однородных примитивных матриц [2,3]. С точки зрения графов, рассматриваемые в этих работах матрицы соответствуют орграфам. В данной работе рассматриваются экспоненты неориентированных однородных графов. В [4] исследуется вопрос о минимальном числе дуг (рёбер) у орграфов (графов) с экспонентом равным 2. В частности, для неориентированных графов с экспонентом 2 минимальное число рёбер есть (3n _ 3)/2 для нечётного n и (3n _ 2)/2 для чётного n. Этот результат удалось уточнить для однородных графов. Однородным или регулярным n-вершинным графом порядка p называется простой неориентированный n-вершинный граф, все вершины которого имеют степень p. Множество n-вершинных однородных графов порядка p будем обозначать Rn,p. Очевидно, что любой примитивный граф является связным. Цикл длины 3 будем называть треугольником. Через g(G) обозначим обхват графа G, то есть наименьшую из длин циклов графа G. Так как в неориентированных графах нет петель, то примитивных графов с экспонентом равным 1 не существует, то есть exp(G) > 1. Нас будут интересовать однородные графы с exp(G) = 2. Очевидно, что диаметр таких графов d(G) ^ 2, однако это условие не является достаточным. Теорема 1. Граф G является примитивным с exp(G) = 2 тогда и только тогда, когда d(G) ^ 2 и каждое ребро графа G входит в треугольник. Второе условие теоремы отдельно также не является достаточным. На рис. 1 представлен 10-вершинный регулярный граф порядка 4. Можно заметить, что каждое ребро этого графа входит в треугольник, граф является примитивным, однако его экспонент равен 3. Рис. 1. 10-Вершинный регулярный граф порядка 4 с exp(G) = 3 Если рассматривать произвольные графы, то можно найти пример с меньшим числом вершин. На рис. 2 представлен 7-вершинный граф с exp(G) = 3, каждое ребро которого входит в треугольник. Следствие 1. Пусть G - примитивный граф с exp(G) = 2. Тогда его обхват g(G) = 3. Легко заметить, что любой полный граф Kn при n > 2 является примитивным и exp(Kn) = 2. Так как каждое ребро примитивного графа G с exp(G) = 2 входит в треугольник, то степень всех вершин графа G не ниже 2. Оказывается, оценку минимальной степени вершин графов с экспонентом, равным 2, можно повысить. В [4] получен следующий результат: для неориентированных графов с экспонентом 2 минимальное число рёбер есть (3n - 3)/2 для нечётного n и (3n - 2)/2 для чётного n. С одной стороны, из этого сразу следует Теорема 2. Среди регулярных графов Яга>2 только граф K3 имеет экспонент 2. С другой стороны, кубические графы содержат 3n/2 рёбер и удовлетворяют условию из работы [4]. Однако получен следующий результат. Теорема 3. Примитивных n-вершинных кубических графов с экспонентом 2 при n > 4 не существует. Теорема 4. Если p > n/2, то любой n-вершинный регулярный граф порядка p является примитивным с экспонентом 2. В [2] доказывается, что однородные ориентированные графы порядка p (степени исхода и захода каждой вершины равны p) с экспонентом 2 могут быть при следующих значениях n: p +1 ^ n ^ 2p - 1. Если рассматривать каждое ребро неориентированного графа как пару встречных дуг, то однородный неориентированный граф порядка p можно рассматривать как однородный ориентированный граф порядка 2p. Тогда оценка для неориентированных графов принимает вид p +1 ^ n ^ 4p - 1. Нижняя оценка достигается для полных графов . Был проведён вычислительный эксперимент с использованием кластера высокопроизводительных вычислений ПРЦ НИТ СГУ по подсчёту регулярных графов с экспонентом, равным 2, и числом вершин до 16. Результаты для 4-, 5- и 6-регулярных графов представлены в таблице. Для генерации регулярных графов использовалась программы GENREG [5] и DSR Generator [6]. Вычисления показывают, что верхняя оценка может быть улучшена. Рис. 3. 11-Вершинный регулярный граф порядка 4 с exp(G) = 2 Количество n-вершинных р-регулярных графов с экспонентом равным 2 n р = 4 р = 5 р = 6 4 0 0 0 5 1 0 0 6 1 1 0 7 2 0 1 8 2 3 1 9 3 0 4 10 0 24 21 11 1 0 266 12 0 210 5457 13 0 0 135775 14 0 116 2806846 15 0 0 40242765 16 0 2 337592332 На рис. 3 приведено изображение 11-вершинного 4-регулярного графа с экспонентом 2 [7].

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