Реберно-транзитивный граф
- Реберно-транзитивный граф в теории графов — граф G, для которого существует автоморфизм, отображающий ребра e1 и e2.
- Граф является транзитивным по ребрам, если его группа автоморфизмов действует транзитивно на ребрах.
- Число связанных простых реберно-транзитивных графов с n вершинами имеет определенную последовательность в OEIS.
- Реберно-транзитивные графы включают симметричные графы, такие как вершины и ребра куба.
- Каждый связный реберно-транзитивный граф, который не является вершинно-транзитивным, должен быть двудольным и либо полусимметричным, либо бирегулярным.
- Существуют (n-1) / 2 реберно-транзитивных графа для нечетных n и (n-2) для четных n.
- Дополнительные реберные транзитивные графы могут быть сформированы как подграфы полных двудольных графов при определенных условиях.
- Альтернативной конструкцией для некоторых реберно-транзитивных графов является добавление вершин к серединам ребер симметричного графа.
- Транзитивный по ребрам граф, который также является правильным, но не транзитивным по вершинам, называется полусимметричным.
Полный текст статьи: