Автоморфизм графа есть отображение множества вершин на себя, сохраняющее смежность.Ф. Харари Теория графов стр. 190 Множество таких автоморфизмов образует вершинную группу графа или просто группу графа. Группа подстановок на множестве ребер называется реберной группой графа, которая тесно связана с вершинной:
Реберная и вершинная группы графа изоморфны тогда и только тогда, когда имеется не более одной изолированной вершины, и нет компонент связности состоящих из единственного ребра.Ф. Харари Теория графов стр. 192
Граф, для которого единственный возможный автоморфизм это тождественное отображение, называется асимметрическим. Наименьшее асимметрическое дерево имеет семь вершин, а наименьший асимметрический граф шесть вершин и столько же ребер.
Для любой конечной группы найдётся такой конечный неориентированный граф, что его группа автоморфизмов изоморфна данной. Результат получен Р. Фрухтом, в основе доказательства — преобразование цветного графа группы, обобщения графа Кэли.Ф. Харари Теория графов стр. 198—201О. Оре Теория графов стр. 317
См. также АТ-группа Автоморфизм Гомоморфизм графов Характерная раскраска
Примечания
Категория:Алгебраическая теория графов