В теории графов рёберно-транзитивным () называется такой граф G , для двух любых рёбер которого e1 и e2 существует автоморфизм, отображающий e1 в e2.
Другими словами, граф рёберно-транзитивен, если его группа автоморфизма действует транзитивно на его рёбрах.
Примеры и свойства
Рёберно-транзитивные графы включает все полные двудольные графы , и все симметричные графы, такие как вершины и рёбра куба. Симметричные графы также вершинно-транзитивны (если они связны), но в общем случае рёберно-транзитивные графы не обязательно вершинно-транзитивны. Граф Грея является примером графа, который является рёберно-транзитивным, но не вершинно-транзитивным. Все такие графы являются двудольными и поэтому могут быть раскрашены всего в два цвета.
Рёберно-транзитивный граф, являющийся также регулярным, но не вершинно-транзитивным, называется полусимметричным. Граф Грея снова служит примером. Рёберно-транзитивный граф должен быть двудольным и либо полусимметричным, либо
См. также (в геометрии)
Примечания
Литература
Ссылки
Категория:Алгебраическая теория графов Категория:Семейства графов