N-Звездный граф

[math]\displaystyle{ n }[/math]-Звездный граф ([math]\displaystyle{ n }[/math]-Star graph) — неориентированный граф [math]\displaystyle{ \,S_{n} }[/math] с [math]\displaystyle{ \,n! }[/math] вершинами, помеченными [math]\displaystyle{ \,n! }[/math] перестановками на символах [math]\displaystyle{ \,1, 2, \ldots, n }[/math]. Между вершинами [math]\displaystyle{ \,u }[/math] и [math]\displaystyle{ \,v }[/math] существует ребро тогда и только тогда, когда существует транспозиция [math]\displaystyle{ \,\pi[1,i], \; 2 \leq i \leq n }[/math], такая, что [math]\displaystyle{ \,\pi[1,i](u) = v }[/math]. Граф [math]\displaystyle{ \,S_{n} }[/math] есть [math]\displaystyle{ \,(n-1) }[/math]-связный симметричный граф Кэлли. Граф [math]\displaystyle{ \,S_{n} }[/math] изоморфен диаграмме Хассе инверсионного частично упорядоченного множества [math]\displaystyle{ {\mathcal I}_{n} }[/math]

Литература

• Workshop. Cadenabbia, 1996 // Lect. Notes Comp. Sci., 1997, vol. 1197.