Граф-звезда — связный граф в котором всё рёбра исходят из одной вершины.
Звезда с <math>k+1</math> вершиной обычно обозначается <math>S_k</math>, при этом <math>k</math> называют порядком звезды.
дерево с одним внутренним узлом и <math>k</math> листьями. Кроме того, некоторые авторы определяют <math>S_k</math> как дерево порядка <math>k</math> с максимальным диаметром 2; тогда граф-звезда <math>k>2</math> имеет <math>k-1</math> листьев.
Граф-звезда с тремя ребрами называется лапа, клешня или тринога[2].
Граф-звезда Sk обладает Шаблон:Не переведено 3, когда k чётно, и не обладает, если k нечётно.
Граф-звезда также может быть описан как связный граф, в котором не более одной вершины имеет степень больше единицы.
Отношение к другим видам графов
Графы-клешни важны в определении графов без клешней, графов, которые не имеют подграфов, являющихся клешнями[3][4].
Граф-звезда является особым видом дерева. Как и любое дерево, граф-звезда может быть закодирован при помощи Шаблон:Не переведено 2; последовательность Прюфера для графа-звезды K1,k состоит из k − 1 копии центральной вершины[5].
