К вопросу о критерии равенства экспонента регулярного примитивного графа числу 3 | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/51

К вопросу о критерии равенства экспонента регулярного примитивного графа числу 3

Рассматривается вопрос поиска критерия равенства числу 3 экспонента регулярного примитивного графа. Получено несколько необходимых и несколько достаточных условий и показано, что ни одно из них не может быть критерием. Проведён вычислительный эксперимент для определения доли примитивных регулярных графов с экспонентом 3, на которых полученные условия не являются критериями. Получен критерий для графов диаметра 2.

About a criterion of equality to 3 for exponent of regular primitive graph.pdf Будем рассматривать простые неориентированные графы. Напомним некоторые определения. Регулярным или однородным графом порядка p называется граф, все вершины которого имеют степень p. Диаметром d(G) связного графа G называется наибольшая длина кратчайшего пути между всеми парами вершин графа G. Связный граф G называется примитивным, если между любыми двумя вершинами этого графа (в том числе из вершины в саму себя) существует маршрут длины k для некоторого k £ N. Минимальное k с таким свойством называется экспонентом этого примитивного графа и обозначается exp(G). Ряд работ посвящены исследованию примитивных регулярных графов [1-3]. Данная работа направлена на поиск критерия равенства экспонента примитивного графа числу 3. Некоторые результаты получены в [4], здесь они дополняются. Завершён вычислительный эксперимент с использованием кластера высокопроизводительных вычислений ПРЦ НИТ СГУ по подсчёту регулярных графов с экспонентом 3, в рамках которого построена таблица числа примитивных регулярных графов со степенью p ^ 9, числом вершин n ^ 16 и экспонентом 3. В табл. 1 приводится результат работы программы - число графов с экспонентом 3 для различных n и p. Символ « -» означает, что графов с такими n и p не существует (p ^ n или произведение pn нечётно). Серый фон клетки означает, что все связные регулярные графы со степенью p и числом вершин n имеют экспонент 2. В [5] показано, что это верно при p > n/2. Таблица 1 Число графов с экспонентом 3 для различных n и p n Р 3 4 5 6 7 8 9 4 0 - - - - - - 5 - 0 - - - - - 6 1 0 0 - - - - 7 - 0 - 0 - - - 8 1 3 0 0 0 - - 9 - 11 - 0 - 0 - 10 1 41 35 0 0 0 0 11 - 143 - 0 - 0 - 12 1 568 7 506 2 391 0 0 0 13 - 2403 - 232 080 - 0 - 14 0 10 377 3 093 569 18 801 129 2 757433 0 0 15 - 42197 - 1429 344 906 - 0 - 16 0 151684 1797 671 946 112 705 503 963 467 764 092 656 34 831303 586 0 Очевидно, что у примитивного графа с экспонентом 3 диаметр может быть 2 или 3. Для упрощения дальнейших рассуждений доказано вспомогательное утверждение - необходимое условие примитивности графа с экспонентом 3. Утверждение 1. В примитивном графе с экспонентом 3 каждая вершина должна лежать хотя бы на одном цикле длины 3. Условие не является достаточным. Например, в полном 3-вершинном графе K3 каждая вершина лежит на цикле длины 3, однако его экспонент равен 2. Очевидно, что данный контрпример является минимальным по числу вершин. Помимо этого, нетрудно найти такие регулярные графы и с экспонентом больше 3. Например, на рис. 1 приводится 3-регулярный примитивный граф с 12 вершинами и экспонентом 4, в котором каждая вершина также лежит хотя бы на одном цикле длины 3. Данный контрпример также является минимальным по числу вершин и рёбер. Таким образом приходим к выводу, что в достаточное условие требуется включить ограничение на диаметр графа. Рассмотрим несколько таких достаточных условий, которые, однако, не являются необходимыми. Рис. 1 Утверждение 2. Если в графе G с диаметром d(G) ^ 3 каждое ребро входит в состав некоторого цикла длины 3, то граф G является примитивным с экспонентом exp(G) ^ 3, причём если d(G) = 3, то exp(G) = 3. На рис. 2 представлен минимальный по числу вершин регулярный граф, который показывает, что данное условие не является необходимым: в нём ребро между вершинами 3 и 5 (аналогично для ребра между вершинами 4 и 6) не лежит ни на одном цикле длины 3. В табл. 2 приведено количество контрпримеров для различных n и p. Можно сделать вывод, что большая доля примитивных регулярных графов с экспонентом 3 не удовлетворяет условию утверждения 2. Поэтому усилим его. Утверждение 3. Если в графе G с диаметром d(G) ^ 3 из каждой пары смежных рёбер хотя бы одно входит в состав некоторого цикла длины 3, то граф G является примитивным с экспонентом exp(G) ^ 3, причём если d(G) = 3, то exp(G) = 3. Условие утверждения 3 также не является необходимым. На рис. 3 изображён минимальный по числу вершин регулярный граф, для которого условие не выполняется: рёбра (5,6) и (5, 8) смежны и оба не лежат ни на одном цикле длины 3. Табл. 3 аналогична табл. 2. Из неё видно, что число контрпримеров уменьшилось в несколько раз, однако всё ещё велико. Однако удалось получить критерий для графов с диаметром 2. Теорема 1. В графе с диаметром 2, в котором каждая вершина лежит хотя бы на одном цикле длины 3, между любыми двумя вершинами (в том числе из вершины в себя) существует маршрут длины 3. Следствие 1. Граф с диаметром 2, в котором каждая вершина лежит хотя бы на одном цикле длины 3, является примитивным и его экспонент меньше или равен 3. Теорема 2. Граф с диаметром 2 является примитивным и имеет экспонент 3 тогда и только тогда, когда каждая его вершина лежит хотя бы на одном цикле длины 3 и существует хотя бы одно ребро, не лежащее ни на одном цикле длины 3.

Ключевые слова

примитивный граф, регулярный граф, экспонент графа, primitive graph, regular graph, graph exponent

Авторы

ФИООрганизацияДополнительноE-mail
Лось Илья ВикторовичСаратовский государственный университет им. Н. Г. Чернышевскогоаспирантlos.ilia.ru@gmail.com
Абросимов Михаил БорисовичСаратовский государственный университет им. Н. Г. Чернышевскогодоктор физико-математических наук, заведующий кафедройmic@rambler.ru
Всего: 2

Ссылки

Jin M., Lee S. G., and Seol H. G. Exponents of r-regular primitive matrices // Inform. Center Math. Sci. 2003. V.6. No. 2. P. 51-57.
Bueno M. I. and Furtado S. On the exponent of r-regular primitive matrices // ELA. Electr. J. Linear Algebra. 2008. V. 17. P. 28-47.
Kim B., Song B., and Hwang W. Nonnegative primitive matrices with exponent 2 // Linear Algebra and its Appl. 2005. No. 407. P. 162-168.
Лось И. В., Абросимов М. Б. К вопросу о максимальном числе вершин в примитивных регулярных графах с экспонентом 3 // Прикладная дискретная математика. Приложение. 2018. №11. С. 112-114.
Абросимов М. Б., Костин С. В. К вопросу о примитивных однородных графах с экспонентом, равным 2 // Прикладная дискретная математика. Приложение. 2017. №10. С. 131-134.
 К вопросу о критерии равенства экспонента регулярного примитивного графа числу 3 | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/51

К вопросу о критерии равенства экспонента регулярного примитивного графа числу 3 | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/51