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