Вершинно-транзитивный граф
- Вершинно-транзитивный граф — граф G, в котором существует автоморфизм, действующий транзитивно на его вершины.
- Каждый симметричный граф без изолированных вершин является вершинно-транзитивным.
- Не все вершинно-транзитивные графы симметричны, и не все правильные графы являются вершинно-транзитивными.
- Конечные примеры вершинно-транзитивных графов включают симметричные графы и графы Кэли.
- Реберная связность связного вершинно-транзитивного графа равна степени d, а вершинная связность будет по меньшей мере 2 (d + 1)/3.
- Бесконечные примеры вершинно-транзитивных графов включают бесконечные пути, правильные деревья и графы Кэли.
Полный текст статьи: