Граф-звезда

• S_k — это полный двудольный граф K_1,k.^[1].

• дерево с одним внутренним узлом и ${\displaystyle k}$ листьями. Кроме того, некоторые авторы определяют ${\displaystyle S_{k}}$ как дерево порядка ${\displaystyle k}$ с максимальным диаметром 2; тогда граф-звезда ${\displaystyle k>2}$ имеет ${\displaystyle k-1}$ листьев.

Граф-звезда с тремя ребрами называется лапа, клешня или тринога ^[2].

Граф-звезда S_k обладает изяществом вершин^[англ.], когда k чётно, и не обладает, если k нечётно.

Граф-звезда также может быть описан как связный граф, в котором не более одной вершины имеет степень больше единицы.

Графы-клешни важны в определении графов без клешней, графов, которые не имеют подграфов, являющихся клешнями^[3][4].

Граф-звезда является особым видом дерева. Как и любое дерево, граф-звезда может быть закодирован при помощи последовательности Прюфера (англ. Prüfer sequence); последовательность Прюфера для графа-звезды K_1,k состоит из k − 1 копии центральной вершины^[5].

Множество расстояний между вершинами графа-клешни представляет собой пример метрического пространства, которое не может быть встроено изометрически в евклидово пространство любой размерности^[6].

Топология компьютерной сети «Звезда», построенная в виде графа-звезды, играет важную роль в распределённых вычислениях.