такой граф, что для любых двух заданных вершин v и w, находящихся на расстоянии i, и любых двух вершин x и y, находящихся на том же расстоянии, су Из Википедии, свободной энциклопедии
Дистанционно-транзитивный граф (англ.distance-transitive graph) — граф, в котором любая упорядоченная пара вершин переводится в любую другую упорядоченную пару вершин с тем же расстоянием между вершинами одним из автоморфизмов графа.
Близким понятием является дистанционно-регулярный граф, однако природа их разная. Если дистанционно-транзитивный граф определяется исходя из симметрии графа через условие автоморфизма, то дистанционно-регулярный граф определяется из условия его комбинаторной регулярности. Каждый дистанционно-транзитивный граф является дистанционно-регулярным, однако обратное не справедливо. Это было доказано в 1969 году, еще до введения в обиход термина «дистанционно-транзитивный граф».
Полностью классифицированы дистанционно-регулярные графы степеней меньших 13.
Существует несколько различных по форме, но одинаковых по смыслу определений дистанционно-транзитивного графа. Предполагается, что граф — неориентированный, связанный и ограниченный. В определении используются понятия расстояние между вершинами графа и автоморфизм графа:
Расстояние между двумя вершинами графа есть количество рёбер по наикратчайшему пути, соединяющему и
Автоморфизм графа — взаимно однозначное отображение множества вершин графа на себя, сохраняющее смежность вершин.
Группа автоморфизмов графа — множество автоморфизмов графа.
Неориентированный, связный, ограниченный граф называется дистанционно-транзитивным, если для двух любых упорядоченных пар его вершин и , таких что существует автоморфизм графа , такой что
Пусть неориентрированный, связный, ограниченный граф обладает группой автоморфизмов . Граф называется дистанционно-транзитивным, если для всех вершин , таких что , существует автоморфизм , который отображает и
Неориентированный связный конечный граф без петель и кратных ребер называется дистанционно-транзитивным, если его группа автоморфизмов действует транзитивно на упорядоченных парах равноудаленных вершин
Пусть — связный граф диаметра и — его группа автоморфизмов. дистанционно-транзитивна на , если она транзитивна на каждом множестве , где . Граф является дистанционно-транзитивным, если его группа автоморфизмов является дистанционно-транзитивной на нем.
Пусть неориентированный, связанный, ограниченный граф обладает группой автоморфизмов . Пусть есть подгруппа . Граф называется -дистанционно-транзитивным (англ.-distance-transitive), если для каждой четвёрки вершин , таких что , существует автоморфизм , который отображает и . Дистанционно-транзитивным называется граф, который является -дистанционно-транзитивным для некоторой подгруппы группы автоморфизмов графа.
Другими словами, есть -дистанционно-транзитивный граф, если подгруппа действует транзитивно на множестве при каждом .
Пусть есть неориентированный, связанный, ограниченный граф, а две его вершины находятся на расстоянии друг от друга. Все вершины , инцидентные к вершине , можно разбить на три множества , и в зависимости от их расстояния до вершины :
, , .
Если граф дистанционно-транзитивный, то мощности (кардинальные числа) множеств не зависят от вершин , а зависят только от расстояния и называются числами пересечений.
Набор чисел пересечений
называется массивом пересечений дистанционно-транзитивного графа[7][8].
Массив пересечений дистанционно-регулярного графа степени . Так как дистанционно-транзитивный граф является регулярным, то числа пересечений и . Более того, . Поэтому массив пересечений дистанционно-регулярного графа можно записать как[4][7][8]:
На первый взгляд дистанционно-транзитивный граф и дистанционно-регулярный граф являются очень близкими понятиями. Действительно, каждый дистанционно-транзитивный граф является дистанционно-регулярным. Однако их природа разная. Если дистанционно-транзитивный граф определяется исходя из симметрии графа через условие автоморфизма, то дистанционно-регулярный граф определяется из условия его комбинаторной регулярности[19].
Дистанционно-транзитивный граф является вершинно-транзитивным, и для него определены числа пересечений. Для дистанционно-регулярный графа через комбинаторную регулярность также определены числа пересечений. Из дистанционно-транзитивности графа следует его дистанционно-регулярность, но обратное неверно[10].
Это было доказано в 1969 г., еще до введения в обиход термина «дистанционно-транзитивный граф», группой советских математиков (Г. М. Адельсон-Вельский, Б. Ю. Вейсфелер, А. А. Леман, И. А. Фараджев)[20][10]. Наименьший дистанционно-регулярный граф, не являющийся дистанционно-транзитивным, — это граф Шрикханде. Единственный тривалентный граф этого типа — это 12-клетка Татта, граф с 126 вершинами[10].
Первый общий результат в классификации дистанционно-транзитивных графов был получен в Биггзом и Смитом [21] в 1971 году, где были классифицированы графы степени три. В течение последующих десяти-пятнадцати лет центральной проблемой в изучении дистанционно-транзитивных графов была классификация дистанционно-транзитивных графов малых степеней[22]. Дистанционно-транзитивные графы степени четыре были полностью классифицированы Смитом[23][24].
В 1983 году Камерон, Прегер, Саксл и Зайц[25] и независимо в 1985 году Вайс[26] доказали, что для любой степени большей двух существует ограниченное число дистанционно-транзитивных графов[27].
Дистанционно-транзитивные графы степени больше трёх
Все дистанционно-транзитивные графы степени известны[28]. Все дистанционно-транзитивных графы степени (валентности) четыре () были получены Д. Смитом в 1973-74 годах[23][24], а пятой, шестой и седьмой степеней в 1984 году А. А. Ивановым, А. В. Ивановым и И. А. Фараджевым[29].
В 1986 году А. А. Ивановым и А. В. Ивановым были получены все дистанционно-транзитивные графы степеней от до [30].
Походы к классификации
Списки дистанционно-транзитивных графов малых степеней были получены в рамках подхода, основанном на рассмотрении стабилизатора отдельной вершины и теоремах, ограничивающих диаметр графа. А. А. Иванов назвал этот подход «локальным». «Глобальный» же подход основывается на рассмотрении действия группы автоморфизмов на множестве вершин. Этот подход позволяет классифицировать дистанционно-транзитивные графы, действие группы на которых примитивно. Из них затем конструируют все остальные[22].
Cameron P. J., Praeger C. E., Saxl J., and Seitz G. M.On the Sims conjecture and
distance-transitive graphs// Bull. London Math. Soc.— 1983.— Vol.15.— P.499—506.
Biggs N.Distance-Transitive Graphs//Finite Groups of Automorphisms(англ.).— London & New York: Cambridge University Press, 1971.— Vol.6.— P.86—96.— (London Mathematical Society Lecture Note Series).
Biggs N. L.Distance-Transitive Graphs//Algebraic Graph Theory(англ.).— 2nd edition.— Cambridge University Press, 1993.— P.155–163.— 205p.
Brouwer A. E., Cohen A. M., Neumaier A.Distance-Transitive Graphs//Distance-Regular Graphs(англ.).— New York: Springer-Verlag, 1989.— P.214—234.
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).
Godsil C., Royle G.Distance-Transitive Graphs//Algebraic Graph Theory(англ.).— New York: Springer-Verlag, 2001.— Vol.207.— P.66—69.— (Graduate Texts in Mathematics).— doi:10.1007/978-1-4613-0163-9.
Ivanov A. A., Ivanov A. V.Distance-transitive graphs of valency k, 8 < k < 13//Algebraic, Extremal and Metric Combinatorics 1986(англ.)/Deza, M., Frankl, P., & Rosenberg, I. (Eds.).— Cambridge: Cambridge University Press, 1988.— P.112—145.— (London Mathematical Society Lecture Note Series).— doi:10.1017/CBO9780511758881.
Lauri J., Scapelatto R.Topics in Graph Automorphisms and Reconstruction(англ.).— 2nd edition.— Cambridge: Cambridge University Press, 2016.— 188p.— (London Mathematical Society Lecture Note Series).— doi:10.1017/CBO9781316669846.
Biggs N. L., Smith D. H.On trivalent graphs(англ.)// Bulletin of the London Mathematical Society.— 1971.— Vol. 3, iss. 2.— P. 155—158.— doi:10.1112/blms/3.2.155.
Smith D. H.On tetravalent graphs(англ.)// J. Lodon Math. Soc.— 1973.— Vol. 6.— P. 659—662.
Smith D. H.Distance-transitive graphs of valency four(англ.)// J. Lodon Math. Soc.— 1974.— Vol. 8.— P. 377—384.
Van Bon J.Finite primitive distance-transitive graphs(англ.)// European Journal of Combinatorics.— 2007.— Vol. 28, iss. 2.— P. 517—532.— doi:10.1016/j.ejc.2005.04.014.