Вершинно-транзитивний граф

В теорії графів вершинно-транзитивним графом називається граф G такий, що для будь-яких двох вершин v₁ і v₂ графу G існує автоморфізм

f:V(G)\rightarrow V(G)\

такий, що

f(v_{1})=v_{2}.\

Іншими словами граф вершинно-транзитивний, якщо його група автоморфізму діє транзитивно щодо вершин^[1]. Граф вершинно-транзитивний тоді і тільки тоді, коли результати автоморфізмів його доповнення ідентичні.

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

Приклади скінченних графів

Ребра зрізаного тетраедра формують вершинно-транзитивний граф (одночасно і граф Келі), не є симетричним.

Множина скінченних вершинно-транзитивних графів включає симетричні графи (такі як граф Петерсена, граф Хівуда і вершини та ребра правильних багатогранників). Скінченні графи Келі (такі як сполучені в куб цикли^[en]) є вершинно-транзитивними, як і вершини і ребра архімедового тіла (хоча тільки 2 з них симетричні). Поточнік, Спіга і Веррет (Primoz Potočnik, Pablo Spiga, Gabriel Verret) створили перепис всіх зв'язних кубічних (тобто з вершинами степеня 3) вершинно-транзитивних графів з кількістю вершин, що не перевищує 1280^[2].

Властивості

Реберна зв'язність вершинно-транзитивного графу дорівнює степеню d, в той час як вершинна зв'язність буде принаймні 2(d+1)/3^[3]. Якщо степінь дорівнює 4 або менше, або граф також реберно-транзитивний, або граф є мінімальним графом Келі, то вершинна зв'язність буде рівною d^[4].

Приклади нескінченних графів

До нескінченних вершинно-транзитивних графів належать:

нескінченні шляхи (нескінченні в обох напрямках);
нескінченні регулярні дерева, тобто граф Келі вільної групи;
графи однорідних паркетів^[ru] (див. повний список^[en] паркетів на площині), включно зі всіма паркетами з правильних багатокутників;
нескінченні графи Келі;
Графи Радо.

Два зліченних вершинно-транзитивних графи називаються квазіізометричними, якщо відношення їхніх функцій відстані обмежене знизу і зверху. Відома гіпотеза стверджує, що будь-який нескінченний вершинно-транзитивний граф квазіізоморфний графу Келі. Контрприклад був наведений Райнхардом Дістелем^[de] та Імре Лідером^[en] у 2001-му році^[5]. У 2005-му році Ескін, Фішер і Вайт підтвердили правильність контрприкладу^[6].

Див. також

Примітки

↑ Chris Godsil, Gordon Royle. Algebraic Graph Theory. — New York : Springer-Verlag, 2001. — Т. 207.
↑ Potočnik P., Spiga P. and Verret G. (2012), Cubic vertex-transitive graphs on up to 1280 vertices, Journal of Symbolic Computation
↑ Godsil, C. and Royle, G. Algebraic Graph Theory. — Springer Verlag, 2001.
↑ Babai, L. Technical Report TR-94-10. — University of Chicago, 1996.アーカイブされたコピー. Архів оригіналу за 11 червня 2010. Процитовано 29 серпня 2010.
↑ Reinhard Diestel, Imre Leader. [1]. — Т. 14. — DOI:10.1023/A:1011257718029.
↑ Alex Eskin, David Fisher, Kevin Whyte. Quasi-isometries and rigidity of solvable groups. — 2005.

Посилання

A census of small connected cubic vertex-transitive graphs [Архівовано 7 березня 2016 у Wayback Machine.]. Primož Potočnik, Pablo Spiga, Gabriel Verret, 2012.

[1] Chris Godsil, Gordon Royle. Algebraic Graph Theory. — New York : Springer-Verlag, 2001. — Т. 207.

[2] Potočnik P., Spiga P. and Verret G. (2012), Cubic vertex-transitive graphs on up to 1280 vertices, Journal of Symbolic Computation

[3] Godsil, C. and Royle, G. Algebraic Graph Theory. — Springer Verlag, 2001.

[4] Babai, L. Technical Report TR-94-10. — University of Chicago, 1996.アーカイブされたコピー. Архів оригіналу за 11 червня 2010. Процитовано 29 серпня 2010.

[5] Reinhard Diestel, Imre Leader. [1]. — Т. 14. — DOI:10.1023/A:1011257718029.

[6] Alex Eskin, David Fisher, Kevin Whyte. Quasi-isometries and rigidity of solvable groups. — 2005.

[1]

[2]

[3]

[4]

[5]

[6]