Automorfizam grafa

Automorfizam grafa, svojstvo grafa u teoriji grafova. Predstavlja permutaciju skupa vrhova $V(G)$ koja čuva susjednost. Grupa automorfizama $Aut(P)$ Petersenova grafa je simetrična grupa $S_5$ te je ukupan broj automorfizama jednak 120. Po Lovaszoj slutnji, graf $G$ je tranzitivan po vrhovima ako za svaki par vrhova $u$ i $v$ iz $G$ postoji automorfizam na $G$ koji preslikava $u$ u $v$. Još uvijek nije otkriven niti jedan graf koji je tranzitivan po vrhovima, a da nema Hamiltonov put. Slutnja se pokazala točnom za razne klase grafova, no još uvijek nije pronađen dokaz.

Vidi

• Fruchtov poučak