Дистанционно-транзитивный граф (:nvmguenkuuk-mjgu[nmnfudw ijgs)

Граф Биггса — Смита, наибольший 3-регулярный дистанционно-транзитивный граф

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

Близким понятием является дистанционно-регулярный граф, однако природа их разная. Если дистанционно-транзитивный граф определяется исходя из симметрии графа через условие автоморфизма, то дистанционно-регулярный граф определяется из условия его комбинаторной регулярности. Каждый дистанционно-транзитивный граф является дистанционно-регулярным, однако обратное не справедливо. Это было доказано в 1969 году, еще до введения в обиход термина «дистанционно-транзитивный граф».

Полностью классифицированы дистанционно-регулярные графы степеней меньших 13.

Определения дистанционно-транзитивного графа

Существует несколько различных по форме, но одинаковых по смыслу определений дистанционно-транзитивного графа. Предполагается, что граф $\Gamma =(V,E)$ — неориентированный, связанный и ограниченный. В определении используются понятия расстояние между вершинами графа и автоморфизм графа:

Расстояние $d(u,v)$ между двумя вершинами $u,v\in V(\Gamma )$ графа $\Gamma =(V,E)$ есть количество рёбер по наикратчайшему пути, соединяющему $u$ и $v$
Автоморфизм графа $g:V\rightarrow V$ — взаимно однозначное отображение множества вершин графа на себя, сохраняющее смежность вершин.
Группа автоморфизмов графа $\mathrm {Aut} (\Gamma )$ — множество автоморфизмов графа.

Определение по Годзилу—Ройлу ^[1]

Неориентированный, связный, ограниченный граф $\Gamma =(V,E)$ называется дистанционно-транзитивным, если для двух любых упорядоченных пар его вершин $(u,v)$ и $(x,y)$ , таких что $d(u,v)=d(x,y)$ существует автоморфизм $g$ графа $\Gamma$ , такой что $g:(u,v)\rightarrow (x,y)$

Определение по Биггзу ^[2]^[3]

Пусть неориентрированный, связный, ограниченный граф $\Gamma =(V,E)$ обладает группой автоморфизмов $\mathrm {Aut} (\Gamma )$ . Граф $\Gamma$ называется дистанционно-транзитивным, если для всех вершин $u,v,x,y$ , таких что $d(u,v)=d(x,y)$ , существует автоморфизм $g\in G$ , который отображает $u\rightarrow x$ и $v\rightarrow y$

Определение по Иванову—Иванову—Фараджеву ^[4]

Неориентированный связный конечный граф $\Gamma =(V,E)$ без петель и кратных ребер называется дистанционно-транзитивным, если его группа автоморфизмов $\mathrm {Aut} (\Gamma )$ действует транзитивно на упорядоченных парах равноудаленных вершин

Определение по Коуэну ^[5]

Пусть $\Gamma =(V,E)$ — связный граф диаметра $D$ и $\mathrm {Aut} (\Gamma )$ — его группа автоморфизмов. $\mathrm {Aut} (\Gamma )$ дистанционно-транзитивна на $\Gamma$ , если она транзитивна на каждом множестве $\Gamma _{i}=\left\{(x,y)\in \Gamma \times \Gamma :d(x,y)=i\right\}$ , где $i=0,\,1,\,\ldots ,\,D$ . Граф $\Gamma$ является дистанционно-транзитивным, если его группа автоморфизмов $\mathrm {Aut} (\Gamma )$ является дистанционно-транзитивной на нем.

Определение по Иванову ^[6]

Пусть неориентированный, связанный, ограниченный граф $\Gamma =(V,E)$ обладает группой автоморфизмов $\mathrm {Aut} (\Gamma )$ . Пусть $G$ есть подгруппа $\mathrm {Aut} (\Gamma )$ . Граф $\Gamma$ называется $G$ -дистанционно-транзитивным (англ. $G$ -distance-transitive), если для каждой четвёрки вершин $u,v,x,y$ , таких что $d(u,v)=d(x,y)$ , существует автоморфизм $g\in G$ , который отображает $u\rightarrow x$ и $v\rightarrow y$ . Дистанционно-транзитивным называется граф, который является $G$ -дистанционно-транзитивным для некоторой подгруппы $G$ группы автоморфизмов графа.

Другими словами, $\Gamma$ есть $G$ -дистанционно-транзитивный граф, если подгруппа $G$ действует транзитивно на множестве $\left\{(x,y)\mid x,e\in V(\Gamma ),\,d(x,y)=i\right\}$ при каждом $i$ .

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

Пусть $\Gamma =(V,E)$ есть неориентированный, связанный, ограниченный граф, а две его вершины $u,v\in V(\Gamma )$ находятся на расстоянии $j=d(u,v)$ друг от друга. Все вершины $w$ , инцидентные к вершине $u$ , можно разбить на три множества $A$ , $B$ и $C$ в зависимости от их расстояния $d(v,w)$ до вершины $v$ :

\left\{w\in A\colon d(v,w)=j\right\}

,

\left\{w\in B\colon d(v,w)=j+1\right\}

,

\left\{w\in C\colon d(v,w)=j-1\right\}

.

Если граф $\Gamma$ дистанционно-транзитивный, то мощности (кардинальные числа) множеств $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ не зависят от вершин $u,v$ , а зависят только от расстояния $j=d(u,v)$ и называются числами пересечений.

Набор чисел пересечений

\iota (\Gamma )={\begin{Bmatrix}\ast &c_{1}&c_{2}&\dots &c_{d-1}&c_{d}\\a_{0}&a_{1}&a_{2}&\dots &a_{d-1}&a_{d}\\b_{0}&b_{1}&b_{2}&\dots &b_{d-1}&\ast \\\end{Bmatrix}}

называется массивом пересечений дистанционно-транзитивного графа^[7]^[8].

Свойства

Каждый дистанционно-транзитивный граф является дистанционно-регулярным, однако обратное не справедливо^[4]^[9]^[10]^[11].
Дистанционно-транзитивный граф является вершинно-транзитивным и симметричным^[3].
Массив пересечений дистанционно-регулярного графа степени $k$ . Так как дистанционно-транзитивный граф является регулярным, то числа пересечений $b_{0}=k$ и $c_{1}=1$ . Более того, $a_{i}+b_{i}+c_{i}=k$ . Поэтому массив пересечений дистанционно-регулярного графа можно записать как^[4]^[7]^[8]:

\iota (\Gamma )={\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{d-1}\,;\,1,\,c_{2},\,\dots ,\,c_{d}\end{Bmatrix}}

Примеры

Простейшие примеры дистанционно-транзитивных графов^[5]^[12]^[13]:

полные графы $K_{n}$
полные двудольные графы (биклики) с равными долями $K_{n,n}$
графы гиперкуба $Q_{n}$

Более сложные примеры дистанционно-транзитивных графов:

граф Джонсона^[14]
граф Грассмана^[15]
граф Хемминга^[16]^[17]
граф Ливингстона^[18]

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

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

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

Классификация дистанционно-транзитивных графов

Первый общий результат в классификации дистанционно-транзитивных графов был получен в Биггзом и Смитом ^[21] в 1971 году, где были классифицированы графы степени три. В течение последующих десяти-пятнадцати лет центральной проблемой в изучении дистанционно-транзитивных графов была классификация дистанционно-транзитивных графов малых степеней^[22]. Дистанционно-транзитивные графы степени четыре были полностью классифицированы Смитом^[23]^[24].

В 1983 году Камерон, Прегер, Саксл и Зайц^[25] и независимо в 1985 году Вайс^[26] доказали, что для любой степени большей двух существует ограниченное число дистанционно-транзитивных графов^[27].

Классификация кубических дистанционно-транзитивных графов

В 1971 году Н. Биггз и Д. Смит доказали теорему, что среди кубических (тривалентных) графов существует ровно 12 дистанционно-транзитивных графов^[21]:

Название графа	Число вершин	Диаметр	Обхват	Массив пересечений
Полный граф K₄	4	1	3	{3;1}
Полный двудольный граф K_3,3	6	2	4	{3,2;1,3}
Граф гиперкуба $Q_{3}$	8	3	4	{3,2,1;1,2,3}
Граф Петерсена	10	2	5	{3,2;1,1}
Граф Хивуда	14	3	6	{3,2,2;1,1,3}
Граф Паппа	18	4	6	{3,2,2,1;1,1,2,3}
Граф додекаэдра	20	5	5	{3,2,1,1,1;1,1,1,2,3}
Граф Дезарга	20	5	6	{3,2,2,1,1;1,1,2,2,3}
Граф Коксетера	28	4	7	{3,2,2,1;1,1,1,2}
Граф Татта — Коксетера	30	4	8	{3,2,2,2;1,1,1,3}
Граф Фостера	90	8	10	{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}
Граф Биггса — Смита	102	7	9	{3,2,2,2,1,1,1;1,1,1,1,1,1,3}

Дистанционно-транзитивные графы степени больше трёх

Все дистанционно-транзитивные графы степени $k<13$ известны^[28]. Все дистанционно-транзитивных графы степени (валентности) четыре ( $k=4$ ) были получены Д. Смитом в 1973-74 годах^[23]^[24], а пятой, шестой и седьмой степеней в 1984 году А. А. Ивановым, А. В. Ивановым и И. А. Фараджевым^[29].

В 1986 году А. А. Ивановым и А. В. Ивановым были получены все дистанционно-транзитивные графы степеней от $k=8$ до $k=13$ ^[30].

Походы к классификации

Списки дистанционно-транзитивных графов малых степеней были получены в рамках подхода, основанном на рассмотрении стабилизатора отдельной вершины и теоремах, ограничивающих диаметр графа. А. А. Иванов назвал этот подход «локальным». «Глобальный» же подход основывается на рассмотрении действия группы автоморфизмов на множестве вершин. Этот подход позволяет классифицировать дистанционно-транзитивные графы, действие группы на которых примитивно. Из них затем конструируют все остальные^[22].

Примечания

↑ Godsil and Royle, 2001, p. 66.
↑ Biggs, 1971, p. 87.
↑ ¹ ² Biggs, 1993, p. 118.
↑ ¹ ² ³ Иванов, Иванов и Фараджев, 1984, с. 1704.
↑ ¹ ² Cohen, 2004, p. 223.
↑ Ivanov, 1994, p. 285.
↑ ¹ ² Lauri and Scapelatto, 2016, p. 33.
↑ ¹ ² Biggs, 1993, p. 157.
↑ Lauri and Scapelatto, 2016, p. 34.
↑ ¹ ² ³ ⁴ Brouwer, Cohen and Neumaier, 1989, p. 136.
↑ Cohen, 2004, p. 232.
↑ Godsil and Royle, 2001, p. 66—67.
↑ Biggs, 1993, p. 158.
↑ Brouwer, Cohen and Neumaier, 1989, p. 255.
↑ Brouwer, Cohen and Neumaier, 1989, p. 269.
↑ Van Bon, 2007, p. 519.
↑ Brouwer, Cohen and Neumaier, 1989, p. 261.
↑ Weisstein, Eric W. Livingstone Graph (англ.) на сайте Wolfram MathWorld.
↑ Biggs, 1993, p. 159.
↑ Адельсон-Вельский, Вейсфелер, Леман и Фараджев, 1969.
↑ ¹ ² Biggs and Smith, 1971.
↑ ¹ ² Ivanov, 1994, pp. 288—292.
↑ ¹ ² Smith, 1973.
↑ ¹ ² Smith, 1974.
↑ 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.
↑ Weiss R. On distance-transitive graphs // Bull. London Math. Soc. — 1985. — Vol. 17. — P. 253—256.
↑ Brouwer, Cohen and Neumaier, 1989, p. 214.
↑ Brouwer, Cohen and Neumaier, 1989, p. 221—225.
↑ Иванов, Иванов и Фараджев, 1984.
↑ Ivanov and Ivanov, 1988.

Литература

Книги

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. — 205 p.

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.

Ivanov A. A. Distance-Transitive Graphs and Their Classification (англ.) // Faradžev I. A., Ivanov A. A., Klin M. H., Woldar A. J. (eds.) Investigations in Algebraic Theory of Combinatorial Objects. Mathematics and Its Applications (Soviet Series). — Dordrecht: Springer, 1994. — Vol. 84. — P. 283—378. — doi:10.1007/978-94-017-1972-8.
Lauri J., Scapelatto R. Topics in Graph Automorphisms and Reconstruction (англ.). — 2nd edition. — Cambridge: Cambridge University Press, 2016. — 188 p. — (London Mathematical Society Lecture Note Series). — doi:10.1017/CBO9781316669846.

Статьи

Адельсон-Вельский Г. М., Вейсфелер Б. Ю., Леман А. А., Фараджев И. А. Об одном примере графа, не имеющего транзитивной группы автоморфизмов // Доклады Академии наук. — 1969. — Т. 185, № 5. — С. 975—976.
Иванов А. А., Иванов А. В., Фараджев И. А. Дистанционно-транзитивные графы степени 5, 6 и 7 // Ж. вычисл. матем. и матем. физ. — 1984. — Т. 24, № 11. — С. 1704–1718.
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.

Ссылки

Weisstein, Eric W. Distance-Transitive Graph (англ.) на сайте Wolfram MathWorld.

[_4d97a26c06d14984-1] Godsil and Royle, 2001, p. 66.

[_c0675601bda94c16-2] Biggs, 1971, p. 87.

[_21b5907c7edb5735-3] ¹ ² Biggs, 1993, p. 118.

[_5c571cb8e2079051-4] ¹ ² ³ Иванов, Иванов и Фараджев, 1984, с. 1704.

[_8b6f029ff850ab1b-5] ¹ ² Cohen, 2004, p. 223.

[_486e092f6647d6a4-6] Ivanov, 1994, p. 285.

[_0619c880e60f4978-7] ¹ ² Lauri and Scapelatto, 2016, p. 33.

[_21b58c7c7edb5076-8] ¹ ² Biggs, 1993, p. 157.

[_0619c880e60f497f-9] Lauri and Scapelatto, 2016, p. 34.

[_12232fa94db8a512-10] ¹ ² ³ ⁴ Brouwer, Cohen and Neumaier, 1989, p. 136.

[_8b6f039ff850ace9-11] Cohen, 2004, p. 232.

[_6e741eeafce669af-12] Godsil and Royle, 2001, p. 66—67.

[_21b58c7c7edb5079-13] Biggs, 1993, p. 158.

[_12269da94dbb95d0-14] Brouwer, Cohen and Neumaier, 1989, p. 255.

[_12269aa94dbb90f5-15] Brouwer, Cohen and Neumaier, 1989, p. 269.

[_e6f6533df06924a3-16] Van Bon, 2007, p. 519.

[_12269aa94dbb90fd-17] Brouwer, Cohen and Neumaier, 1989, p. 261.

[18] Weisstein, Eric W. Livingstone Graph (англ.) на сайте Wolfram MathWorld.

[_21b58c7c7edb5078-19] Biggs, 1993, p. 159.

[_0cdd44bb08854b7d-20] Адельсон-Вельский, Вейсфелер, Леман и Фараджев, 1969.

[_ebd0a9e998fb0baf-21] ¹ ² Biggs and Smith, 1971.

[_e9ecc8126d8cc378-22] ¹ ² Ivanov, 1994, pp. 288—292.

[_4c49e6e5ee6564a0-23] ¹ ² Smith, 1973.

[_c91e10207997cd03-24] ¹ ² Smith, 1974.

[25] 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.

[26] Weiss R. On distance-transitive graphs // Bull. London Math. Soc. — 1985. — Vol. 17. — P. 253—256.

[_122699a94dbb8f2d-27] Brouwer, Cohen and Neumaier, 1989, p. 214.

[_a8426f518fb3cd12-28] Brouwer, Cohen and Neumaier, 1989, p. 221—225.

[_408827513fccd2b5-29] Иванов, Иванов и Фараджев, 1984.

[_3c3e85329c4bfc74-30] Ivanov and Ivanov, 1988.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]