Gráfautomorfizmus

A gráfautomorfizmus egy gráf önmagára való izomorfizmusa.

Legyen ${\displaystyle G:=(V,E)}$ gráf. Egy ${\displaystyle f:V\rightarrow V}$ bijektív függvény gráfautomorfizmus, ha

${\displaystyle \{u,v\}\in E\Leftrightarrow \{f(u),f(v)\}\in E}$.

Tehát a gráfautomorfizmus a gráf csúcsainak olyan p permutációja, melyben bármely két u és v csúcs pontosan akkor szomszédos egymással, ha p(u) és p(v) is szomszédosak.

${\displaystyle G=(V,E)}$	${\displaystyle f:V\rightarrow V}$
	${\displaystyle f(a)=g}$ ${\displaystyle f(b)=h}$ ${\displaystyle f(c)=i}$ ${\displaystyle f(d)=j}$ ${\displaystyle f(g)=a}$ ${\displaystyle f(h)=b}$ ${\displaystyle f(i)=c}$ ${\displaystyle f(j)=d}$

• Gráfautomorfizmusok kompozíciója és inverze is gráfautomorfizmus.
• Egy ${\displaystyle (V,E)}$ gráf automorfizmusai a ${\displaystyle V}$ permutációcsoportjának egy részcsoportját alkotják.

• Gráfizomorfizmus
• Gráfhomomorfizmus
• Csúcstranzitív gráf