Кратко сформулирую границы, докажу их, предложу метод вычисления и обсудю сложность.
1) Общие (тривиальные) верхняя и нижняя границы.
- Нижняя: $|Aut(G)|\ge 1$ (тривиальная автоморфизма — тождественная перестановка).
- Верхняя: $|Aut(G)|\le 12!$, так как $Aut(G)$ — подгруппа симметрической группы на $12$ вершинах. Пример достижения верхней границы: полный граф $K_{12}$ имеет $|Aut(K_{12})|=12!=479001600$.
2) Граница по классам степеней.
Обозначим через $m_d$ число вершин степени $d$. Тогда
$$|Aut(G)|\le \prod _d{m}_d!,$$ потому что любой автоморфизм сохраняет степени вершин и, следовательно, действует перестановкой внутри каждого класса одинаковой степени. Эта граница часто гораздо строже, чем $12!$.
3) Уточнение для компонент связности.
Пусть граф распадается на несвязные компоненты, среди которых для каждого типа изоморфного связного графа $C_i$ встречается ровно $k_i$ копий, и пусть $|Aut(C_i)|=a_i$. Тогда
$$|Aut(G)|=\prod _i(k_i!\cdot a_i^{k_i}),$$ так как можно переставлять копии одного типа и независимо применять внутренние автоморфизмы каждой копии.
4) Достижимость нижней границы.
Нижняя граница $1$ достижима: например, возьмём асимметричный граф на $12$ вершинах. Конкретный пример — дополнение к графу Фрухта (Фрухта — 3-регулярный асимметричный граф на $12$ вершинах); дополнение будет $8$-регулярным (минимальная степень $\ge 4$) и по-прежнему асимметричным, значит $|Aut(G)|=1$.
5) Метод вычисления точного числа автоморфизмов для конкретного графа.
- Практические инструменты: программы nauty/traces, bliss, saucy и т.п. Они выдают образующую систему группы автоморфизмов и порядок группы.
- Идея алгоритма: разбиение вершин по инвариантам (степень, вторая степень соседей и т.д.), индивидуализация и уточнение (individualization–refinement), а затем возвратно-поисковый перебор с отсечениями для поиска всех автоморфизмов / получения канонической метки. Для получения порядка группы используется вычисление базиса и система Шрайера–Симса над полученными порождениями.
- На практике для $n=12$ любая из этих программ даёт результат мгновенно; при необходимости можно и прямым перебором проверять перестановки, но эффективнее пользоваться вышеописанными методами.
6) Вычислительная сложность в общем виде.
- Задача проверки изоморфизма графов (GI) и задача нахождения автоморфизмов (GA) связаны: GA редуцируема к GI и наоборот в полиномиальном времени; худшая сложность общая.
- Наилучший на сегодняшний день теоретический результат (Babai, 2016): GI (а значит и GA) разрешима в квази-полиномиальное время; формально время алгоритма можно записать как $n^{O(\log n)}$ (квази-полиномиальное), где $n$ — число вершин.
- Для классических частных случаев существуют полиномиальные алгоритмы: например, графы с ограниченной максимальной степенью обрабатываются за полиномиальное время (Luks), а на практике nauty/traces очень эффективны на большинстве входов.
- Вывод: в общем случае точный подсчёт $|Aut(G)|$ теоретически занимает квази-полиномиальное время в худшем случае, но для малых $n$ (в частности $n=12$) и в большинстве практических случаев задача решается быстро.
Если нужно, могу привести конкретную последовательность шагов с nauty/traces для вашего графа в виде команд или показать пример вывода (требуется конкретный граф).