スター (グラフ理論)
頂点数が3のスターであるクローはクローフリーグラフ(部分グラフとしてクローを持たないグラフ)の定義で有名である。また、ハスラー・ホイットニー (Hassler Whitney) のグラフ同型定理(一般的に、グラフ同型な線グラフはクローと三角形グラフ K3を除き同型である。)の例外の1つでもある。
スターは木の特殊な場合であるため、木と同様にプリューファー列で表すことができ、スター Sk は中心の頂点を k-1 回並べた列となる。
スターの考え方を用いて定義されているグラフ不変量がいくつかある。スターの樹化数は森に含まれる木が全てスターとなるような分割を行った際の最小の森の数として定義されている。スター彩色数は、2つの色グループで彩色した場合、同じ色で接続された頂点グループが全てスターとなる彩色数である。分枝幅が1であるというのは、連結している分枝がそれぞれスターであることと同値である。
スター もしくは星Sk は、グラフ理論の用語の1つであり、ただ1つの頂点とそれにつながる k 個の葉のみを持つグラフである。また、スターは完全2部グラフ K1, kでもある。スター Sk を直径が2で次数が k である木とする人も存在し、この場合 2 < k であり葉の数は k-1 である。
頂点が3個の星は特別にクローもしくは爪と呼ぶ。
スター Sk は k が偶数のときには edge-graceful であり、 k が奇数の場合はそうでない。スターは頂点推移グラフであり、 1 < k においてグラフの直径は2であり、内周は ∞ である。また、スターは自己同型群を持つ。すなわち、 k 次の対称群である。
スターは、(最大でも)1つの頂点の次数が1より大きい、連結グラフともいえる。