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

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

Визначення

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

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

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

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

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

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

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

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

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

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

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

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

повні графи повні двочасткові графи (бікліки) з рівними частками графи гіперкуба

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

граф Джонсона

граф Геммінга

граф Перкеля

Класифікація кубічних дистанційно-транзитивних графів 1971 року і Сміт у роботі довели теорему, що серед тривалентних графів існує всього лише 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} Повний список дистанційно-транзитивних графів відомий для деяких степенів, більших від трьох, але класифікація дистанційно-транзитивних графів з довільно великим степенем залишається відкритою.

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

Примітки

Література

Ранні роботи

Огляди

.

Посилання