Полутранзитивный граф
В математической области теории графов полутранзитивный граф — это граф , который является одновременно вершинно-транзитивным и реберно-транзитивным , но не симметричным . [1] Другими словами, граф полутранзитивен, если его группа автоморфизмов действует транзитивно как на его вершины, так и на его ребра, но не на упорядоченные пары связанных вершин.
Каждый связный симметричный граф должен быть вершинно-транзитивным и реберно-транзитивным , и обратное верно для графов нечетной степени: [2] так что полутранзитивных графов нечетной степени не существует. Однако существуют полутранзитивные графы четной степени. [3] Наименьшим полутранзитивным графом является граф Холта со степенью 4 и 27 вершинами. [4] [5]
Ссылки [ править ]
- ^ Гросс, Дж.Л.; Йеллен, Дж. (2004). Справочник по теории графов . ЦРК Пресс. п. 491. ИСБН 1-58488-090-2 .
- ^ Бабай, Л (1996). «Группы автоморфизмов, изоморфизм, реконструкция» . В Грэме, Р.; Гретшель, М ; Ловас, Л. (ред.). Справочник по комбинаторике . Эльзевир.
- ^ Бауэр, З. (1970). «Вершинные и реберные транзитивные, но не 1-транзитивные графы» . Канадский математический бюллетень . 13 : 231–237. дои : 10.4153/CMB-1970-047-8 .
- ^ Биггс, Норман (1993). Алгебраическая теория графов (2-е изд.). Кембридж: Издательство Кембриджского университета. ISBN 0-521-45897-8 .
- ^ Холт, Дерек Ф. (1981). «Граф, транзитивный по ребрам, но не транзитивный по дугам». Журнал теории графов . 5 (2): 201–204. дои : 10.1002/jgt.3190050210 . .