В теорії графів вершинно-транзитивним графом називається граф G такий, що для будь-яких двох вершин v1 і v2 графу G існує автоморфізм
такий, що
Іншими словами граф вершинно-транзитивний, якщо його група автоморфізму діє транзитивно щодо вершин. Граф вершинно-транзитивний тоді і тільки тоді, коли результати автоморфізмів його доповнення ідентичні.
Будь-який симетричний граф без ізольованих вершин є вершинно-транзитивним, і будь-який вершинно-транзитивний граф є регулярним. Однак не всі вершинно-транзитивні графи симетричні (наприклад, ребра зрізаного тетраедра), і не всі регулярні графи вершинно-транзитивні (наприклад, граф Фрухта і граф Тітце).
Приклади скінченних графів
Множина скінченних вершинно-транзитивних графів включає симетричні графи (такі як граф Петерсена, граф Хівуда і вершини та ребра правильних багатогранників). Скінченні графи Келі (такі як ) є вершинно-транзитивними, як і вершини і ребра архімедового тіла (хоча тільки 2 з них симетричні). Поточнік, Спіга і Веррет (Primoz Potočnik, Pablo Spiga, Gabriel Verret) створили перепис всіх зв'язних кубічних (тобто з вершинами степеня 3) вершинно-транзитивних графів з кількістю вершин, що не перевищує 1280.
Властивості Реберна зв'язність вершинно-транзитивного графу дорівнює степеню d, в той час як вершинна зв'язність буде принаймні 2(d+1)/3. Якщо степінь дорівнює 4 або менше, або граф також реберно-транзитивний, або граф є мінімальним графом Келі, то вершинна зв'язність буде рівною d.
Приклади нескінченних графів До нескінченних вершинно-транзитивних графів належать:
нескінченні шляхи (нескінченні в обох напрямках); нескінченні регулярні дерева, тобто граф Келі вільної групи; графи (див. паркетів на площині), включно зі всіма паркетами з правильних багатокутників; нескінченні графи Келі; Графи Радо.
Два зліченних вершинно-транзитивних графи називаються квазіізометричними, якщо відношення їхніх функцій відстані обмежене знизу і зверху. Відома гіпотеза стверджує, що будь-який нескінченний вершинно-транзитивний граф квазіізоморфний графу Келі. Контрприклад був наведений та у 2001-му році. У 2005-му році Ескін, Фішер і Вайт підтвердили правильність контрприкладу.
Див. також Реберно-транзитивний граф Гіпотеза Ловаса про гамільтонів цикл Напівсиметричний граф Граф Геммінга
Примітки
Посилання A census of small connected cubic vertex-transitive graphs . Primož Potočnik, Pablo Spiga, Gabriel Verret, 2012.