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]

Литература

[WG'96]