Эта статья входит в число добротных статей

Дистанционно-регулярный граф

Перейти к навигацииПерейти к поиску
Граф Шрикханде — дистанционно-регулярный граф, не являющийся дистанционно-транзитивным

Дистанционно-регулярный граф (англ. distance-regular graph) — такой регулярный граф, у которого для двух любых вершин и , расположенных на одинаковом расстоянии друг от друга, справедливо, что количество вершин, инцидентных к и при этом находящихся на расстоянии от вершины , зависит только от расстояния между вершинами и ; более того, количество вершин, инцидентных к и находящихся на расстоянии от вершины , также зависит только от расстояния .

Дистанционно-регулярные графы были введены Н. Биггсом в 1969 году на конференции в Оксфорде[1], хотя сам термин появился гораздо позже[2].

Определение

Определение дистанционно-регулярного графа[3][4]:

Дистанционно-регулярный граф — это неориентрированный, связанный, ограниченный, регулярный граф валентности и диаметром , для которого справедливо следующее. Существуют натуральные числа

такие, что для каждой пары вершин , отстоящих друг от друга на расстоянии , справедливо:

(1) число вершин, инцидентных и находящихся на расстоянии от , есть ()
(2) число вершин, инцидентных и находящихся на расстоянии от , есть ().

Тогда

есть массив пересечений графа (см. § Массив пересечений), а числа пересечений, где [3][4].

Массив пересечений

Изначально термины «массив пересечений» и «числа пересечений» были введены для описания дистанционно-транзитивных графов[5][6][7].

Пусть есть неориентированный, связанный, ограниченный граф, а две его вершины находятся на расстоянии друг от друга. Все вершины , инцидентные к вершине , можно разбить на три множества , и в зависимости от их расстояния до вершины  :

Если граф дистанционно-транзитивный, то мощности (кардинальные числа) множеств не зависят от вершин , а зависят только от расстояния . Пусть , где есть числа пересечений.

Определим массив пересечений дистанционно-транзитивного графа как:

Если — валентность графа, то , а . Более того, , тогда компактная форма записи массива пересечений есть:

Дистанционно-регулярный и дистанционно-транзитивный графы

На первый взгляд дистанционно-транзитивный граф и дистанционно-регулярный граф являются очень близкими понятиями. Действительно, каждый дистанционно-транзитивный граф является дистанционно-регулярным. Однако их природа разная. Если дистанционно-транзитивный граф определяется исходя из симметрии графа через условие автоморфизма, то дистанционно-регулярный граф определяется из условия его комбинаторной регулярности[3].

Следствием автоморфизма дистанционно-транзитивного графа является его регулярность. Соответственно, для регулярного графа можно определить числа пересечений. С другой стороны для дистанционно-регулярного графа существует комбинаторная регулярность, и для него также определены числа пересечений (см. § Массив пересечений), однако автоморфизм из этого не следует[8][9].

Из дистанционно-транзитивности графа следует его дистанционно-регулярность, но обратное неверно[8]. Это было доказано в 1969 г., еще до введения в обиход термина «дистанционно-транзитивный граф», группой советских математиков (Г. М. Адельсон-Вельский, Б. Ю. Вейсфелер, А. А. Леман, И. А. Фараджев)[10][8]. Наименьший дистанционно-регулярный граф, не являющийся дистанционно-транзитивным, — это граф Шрикханде. Единственный тривалентный граф этого типа — это 12-клетка Татта, граф с 126 вершинами[8].

Свойства

Свойства массива пересечений дистанционно-регулярного графа

Массив пересечений дистанционно-регулярного графа обладает следующими свойствами[11][12]:

  • Каждая вершина имеет постоянное число вершин , отстоящих от нее на расстояние , причем и для всех ;
  • Порядок графа равен ;
  • Число вершин, отстоящих от каждой вершины на расстоянии , выражается через числа пересечений как для всех ;
  • Произведение числа вершин, отстоящих от произвольной вершины на расстоянии , на порядок графа есть четная величина для всех ;
  • Произведение числа вершин, отстоящих от произвольной вершины на расстоянии , на число пересечений на есть четная величина для всех ;
  • Произведение числа пересечений на порядок графа и на его валентность делится на 6;
  • Для чисел пересечений справедливо ;
  • Для чисел пересечений справедливо ;
  • Если , то ;
  • Есть такое , что и .

Матрицы расстояний транзитивно-регулярного графа

Пусть граф — транзитивно-регулярный диаметра , есть число его вершин, а — валентность графа. Определим множество матриц расстояний (англ. distance matrices) размера как[3] :

Свойства матриц расстояний

Матрицы расстояния обладают следующими свойствами[3]:

  • , где есть единичная матрица ;
  • есть обычная матрица смежности графа ;
  • , где есть матрица единиц
  • , где — массив пересечений дистанционно-регулярного графа и
  • существуют такие действительные числа , что для всех , причем есть число пересечений, то есть количество вершин, находящихся на расстоянии от вершины и на расстоянии от вершины при условии расстояния между вершинами и . Отметим, что , , .

Примечания

Литература

  • Адельсон-Вельский Г. М., Вейсфелер Б. Ю., Леман А. А., Фараджев И. А. Об одном примере графа, не имеющего транзитивной группы автоморфизмов // Доклады Академии наук. — 1969. — Т. 185, № 5. — С. 975—976.
  • Biggs N. L. Intersection Matrices for Linear Graphs (англ.) // Combinatorial mathematics and its applications : proceedings of a conference held at the Mathematical Institute, Oxford, from 7-10 July, 1969 / edited by D.J.A. Welsh. — London: Academic press, 1971. — P. 15-23.
  • Biggs N. L. Algebraic Graph Theory (англ.). — 2nd edition. — Cambridge University Press, 1993. — 205 p.
  • Brouwer A., Cohen A. M., Neumaier A. Distance Regular Graphs (англ.). — Berlin, New York: Springer Verlag, 1989. — ISBN 3-540-50619-5, 0-387-50619-5.
  • Cohen A. M. Distance-transitive graphs // Topics in Algebraic Graph Theory (англ.) / edited by L. W. Beineke, R. J. Wilson. — Cambridge University Press, 2004. — Vol. 102. — P. 222—249. — (Encyclopedia of Mathematics and its Applications).
  • van Dam E. R., Koolen J. H., Tanaka H. Distance-regular graphs (англ.) // The Electronic Journal of Combinatorics : Dynamic surveys. — 2006. — No. DS22.
  • Lauri J., Scapelatto R. Topics in Graph Automorphisms and Reconstruction (англ.). — 2nd edition. — Combridge: Combridge University Press, 2016. — 188 p.