Přesný počet automorfismů
Úloha číslo: 3575
Pro každé přirozené \(n\) sestrojte graf \(G_n\), který má přesně \(n\) automorfismů, neboli izomorfismů \(G_n\to G_n\).
Řešení
\(K_1\) má jeden automorfismus, \(K_2\) dva.
Cyklus \(C_k\) má \(2k\) automorfismů \(f\)– pro \(f(v_1)\) lze zvolit \(k\) způsoby a pro \(f(v_2)\) pak jeden ze dvou sousedů \(f(v_1)\), zbytek je pak určen jednoznačně. Tímto jsme pokryli případy pro všechna sudá \(n=2k\).
Konstrukce pro lichá \(n\) může vyjít z podobného principu, jen je třeba hrany \(C_n\) nahradit složitějšími grafy, aby volba \(f(v_2)\) byla jednoznačně určena volbou \(f(v_1)\). Toho lze docílit např. pokud hranu nahradíme cestou délky tři, kde k prvnímu vnitřnímu vrcholu cesty přidáme 1 list a ke druhému dva, viz obrázek.
Má-li původní cyklus vrcholy \(v_1,…,v_k\) v pořadí po směru hodinových ručiček, potom v upraveném grafu posílá každý automorfismus vrchol \(v_1\) na nějaký vrchol stupně dva. Obraz \(v_2\) je už jednoznačně dán, je to první vrchol stupně dva, který následuje po \(f(v_1)\) ve směru hodinových ručiček.
Podobných konstrukcí existuje více.