Дистанційно-транзитивний граф

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

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

Термін дистанційно-транзитивний граф увели Бігс і Сміт 1971 року[1].

Визначення

Повний граф

Визначення дистанційно-транзитивного граф

Нехай неорієнтований, зв'язний, обмежений граф має групу автоморфізмів . Кількість ребер у найкоротшому шляху, що з'єднує називають відстанню між і і позначають як . Нехай  — підгрупа . Граф називають -дистанційно-транзитивним (англ. -distance-transitive якщо для кожної четвірки вершин , таких що , існує автоморфізм , який відображає і .[2]

Іншими словами[2] є -дистанційно-транзитивним графом, якщо підгрупа діє транзитивно на множину .

Масив перетинів

Нехай  — неорієнтований, зв'язний, обмежений граф, а дві його вершини розташовані на відстані одна від одної. Всі вершини , інцідентні вершині можна розбити на три множини , і , залежно від їх відстані до вершини :

Якщо граф дистанційно-транзитивний, то кардинальні числа множин не залежать від вершин і , а залежать тільки від відстані . Нехай , де  числа перетинів.

Визначимо масив перетинів дистанційно-транзитивного графу як[3][4]:

Оскільки дистанційно-транзитивний граф є регулярним, приміром степеня , тоді , , а . Більш того, . Тому масив перетинів дистанційно-регулярного графу часто записують як:

Властивості

Кожен дистанційно-транзитивний граф є дистанційно-регулярним, проте зворотне не справедливе. Це доведено 1969 року, ще до введення в ужиток терміна дистанційно-транзитивний граф, групою радянських математиків[5] (Адельсон-Вельський Г. М., Вейсфейлер Б. Ю., Леман А. А., Фараджев І. А.). Найменший дистанційно-регулярний граф, який не є дистанційно-транзитивним — це граф Шрікханде. Єдиний тривалентний граф цього типу — це 12-клітка Татта, граф зі 126 вершинами.

Дистанційно-транзитивний граф є вершинно-транзитивним і симетричним.

Дистанційно-транзитивні графи мають велике число груп автоморфізмів.

Гігман[6][7] розвинув теорію груп рангу 3. Ці групи є групами автоморфізмів сильно регулярних графів, причому вони діють транзитивно як на множині вершин і ребер, так і на множині пар різних несуміжних вершин. Такі графи є дистанційно транзитивними графами діаметру 2.

Приклади

Найпростіші приклади дистанційно-транзитивних графів:

Складніші приклади дистанційно-транзитивних графів:

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

1971 року Бігс і Сміт у роботі[1] довели теорему, що серед тривалентних графів існує всього лише 12 дистанційно-транзитивних графів:

Назва графу Число вершин Діаметр Обхват Масив перетинів
Повний граф K 4 4 1 3 {3; 1}
Повний двочастковий граф K 3,3 6 2 4 {3,2; 1,3}
Граф Петерсена 10 2 5 {3,2; 1,1}
Граф гіперкуба 8 3 4 {3,2,1; 1,2,3}
Граф Хівуда 14 3 6 {3,2,2; 1,1,3}
Граф Паппа 18 4 6 {3,2,2,1; 1,1,2,3}
Граф Коксетера 28 4 7 {3,2,2,1; 1,1,1,2}
Граф Татта — Коксетера 30 4 8 {3,2,2,2; 1,1,1,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}
Граф Бігса — Сміта 102 7 9 {3,2,2,2,1,1,1; 1,1,1,1,1,1,3}
Граф Фостера 90 8 10 {3,2,2,2,2,1,1,1; 1,1,1,1,2,2,2,3}

Повний список дистанційно-транзитивних графів відомий для деяких степенів, більших від трьох, але класифікація дистанційно-транзитивних графів з довільно великим степенем залишається відкритою.

Найпростіше асимптотичне сімейство дистанційно-транзитивних графів — це графи гіперкубів. Інші сімейства — це складені кубічні графи і квадратні турові графи. Всі три сімейства мають довільно великий степінь.

Примітки

Література

  • Адельсон-Вельский Г.М., Вейсфелер Б.Ю., Леман А.А., Фараджев И.А. Об одном примере графа, не имеющнго транзитивной группы автоморфизмов // Доклады Академии наук.  1969. Т. 185, № 5 (3 листопада). С. 975—976.
  • Biggs N.L., Smith D.H. On trivalent graphs // Bulletin of the London Mathematical Society.  1971. Vol. 3, iss. 2 (3 November). P. 155—158. DOI:10.1112/blms/3.2.155.
  • Biggs N.L. Algebraic Graph Theory. — 2nd. — Cambridge University Press, 1993. — 205 с.
  • Higman D.G. Finite permutation groups of rank 3 // Math. Zeitschr..  1964. — 3 листопада. С. 142—156.
  • Higman D.G. Primitive rank 3 groups with a prime subdegree // Math. Zeitschr..  1966. Т. 91 (3 листопада). С. 70-89.
  • Ivanov A. A. Distance-Transitive Graphs and Their Classification / (eds.) // Investigations in Algebraic Theory of Combinatorial Objects. Mathematics and Its Applications (Soviet Series). — Dordrecht : Springer, 1994. Vol. 84 (3 November). P. 283-378.
  • Lauri J., Scapelatto R. Topics in Graph Automorphisms and Reconstruction. — 2nd. — Combridge : Combridge University Press, 2016. — 188 с.

Ранні роботи

  • Biggs N. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969). — London : Academic Press, 1971. — С. 15—23.
  • Biggs N. Finite Groups of Automorphisms. — London & New York : Cambridge University Press, 1971. — Т. 6. — (London Mathematical Society Lecture Note Series)
  • Smith D.H. Primitive and imprimitive graphs // The Quarterly Journal of Mathematics. Oxford. Second Series.  1971. Vol. 22, iss. 4 (3 November). P. 551—557. DOI:10.1093/qmath/22.4.551.

Огляди

  • Biggs N.L. Distance-Transitive Graphs // Algebraic Graph Theory. — 2nd. — Cambridge University Press, 1993. — С. 155–163.
  • Van Bon J. Finite primitive distance-transitive graphs // European Journal of Combinatorics.  2007. Vol. 28, iss. 2 (3 November). P. 517—532. DOI:10.1016/j.ejc.2005.04.014..
  • Brouwer A.E, Cohen A.M., Neumaier A. Distance-Transitive Graphs // Distance-Regular Graphs. — New York : Springer-Verlag, 1989. — С. 214—234.
  • Cohen A.M. Topics in Algebraic Graph Theory / L. W. Beineke, R. J. Wilson. — Cambridge University Press, 2004. — Т. 102. — С. 222—249. — (Encyclopedia of Mathematics and its Applications)
  • Godsil C., Royle G. Distance-Transitive Graphs // Algebraic Graph Theory. — New York : Springer-Verlag, 2001. — С. 66—69.

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.