Автоморфизм графа

Автоморфизм графа есть отображение множества вершин на себя, сохраняющее смежность.[1] Множество таких автоморфизмов образует вершинную группу графа или просто группу графа. Группа подстановок на множестве ребер называется реберной группой графа, которая тесно связана с вершинной:

Наименьшее асимметрическое дерево

Наименьший асимметрический граф

Реберная и вершинная группы графа изоморфны тогда и только тогда, когда имеется не более одной изолированной вершины, и нет компонент связности состоящих из единственного ребра.[2]

Граф, для которого единственный возможный автоморфизм это тождественное отображение, называется асимметрическим. Наименьшее асимметрическое дерево имеет семь вершин, а наименьший асимметрический граф шесть вершин и столько же ребер.

Для любой конечной группы найдется такой конечный неориентированный граф, что его группа автоморфизмов изоморфна данной.[3] Результат получен Р. Фрухтом, в основе доказательства — преобразование цветного графа группы, обобщения графа Кэли.[4][5]