原文と比べた結果、この記事には多数の（または内容の大部分に影響ある）誤訳 があることが判明しています。情報の利用には注意してください。 正確な表現に改訳できる方を求めています。 (2017年9月
スター もしくは星 Sk は、グラフ理論 の用語の1つであり、ただ1つの頂点とそれにつながる k 個の葉 のみを持つグラフである。また、スターは完全2部グラフ K 1, k でもある。スター Sk を直径が2で次数 が k である木 とする人も存在し、この場合 2 < k であり葉の数は k-1 である。
頂点が3個の星は特別にクロー もしくは爪 と呼ぶ。
スター Sk は k が偶数のときには edge-graceful であり、 k が奇数の場合はそうでない。スターは頂点推移グラフ であり、 1 < k においてグラフの直径 は2であり、内周 は ∞ である。また、スターは自己同型群 を持つ。すなわち、 k 次の対称群である。
スターは、（最大でも）1つの頂点の次数が1より大きい、連結グラフ ともいえる。
頂点数が3のスターであるクロー はクローフリーグラフ（誘導部分グラフ としてクローを持たないグラフ）の定義で有名である[ 1] [ 2] ハスラー・ホイットニー (Hassler Whitney) のグラフ同型定理（一般的に、グラフ同型 な線グラフ はクローと三角形グラフ K 3 を除き同型である[ 3]
スターは木の特殊な場合であるため、木と同様にプリューファー列 で表すことができ、スター Sk は中心の頂点を k-1 回並べた列となる[ 4]
スターの考え方を用いて定義されているグラフ不変量 がいくつかある。スターの樹化数 は森に含まれる木が全てスターとなるような分割を行った際の最小の森の数として定義されている[ 5] スター彩色数 は、2つの色グループで彩色した場合、同じ色で接続された頂点グループが全てスターとなる彩色数である[ 6] 分枝幅 が1であるというのは、連結している分枝がそれぞれスターであることと同値である[ 7]
スターの例。左から順に、S 3 , S 4 , S 5, S 6。
クローの頂点間の距離 の集合 は、任意の次元のユークリッド空間 への等長写像 を持たない、有限距離空間 の一例となる[ 8]
星型（スター型）のネットワーク・トポロジー はスターグラフでモデル化され、分散コンピューティング の分野において重要な概念である。
一定の長さの間隔で辺を識別することで形成したスターの幾何学的実現は、トロピカル幾何学 の曲線の局所モデルとして使用される。トロピカル曲線は、スター型の距離空間の局所的に同型な距離空間として定義される。
^ Faudree, Ralph ; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), “Claw-free graphs — A survey”, Discrete Mathematics 164 (1–3): 87–147, doi :10.1016/S0012-365X(96)00045-3 , MR 1432221 ^ Chudnovsky, Maria ; Seymour, Paul (2005), “The structure of claw-free graphs” , Surveys in combinatorics 2005 , London Math. Soc. Lecture Note Ser., 327 , Cambridge: Cambridge Univ. Press, pp. 153–171, MR 2187738 , http://www.columbia.edu/~mc2775/claws_survey.pdf ^ Whitney, Hassler (January 1932), “Congruent Graphs and the Connectivity of Graphs” , American Journal of Mathematics 54 (1): 150–168, doi :10.2307/2371086 , JSTOR 2371086 , https://jstor.org/stable/2371086 ^ Gottlieb, J.; Julstrom, B. A.; Rothlauf, F.; Raidl, G. R. (2001), “Prüfer numbers: A poor representation of spanning trees for evolutionary search” , Proc. Genetic and Evolutionary Computation Conference , Morgan Kaufmann, pp. 343–350, http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf ^ Hakimi, S. L.; Mitchem, J.; Schmeichel, E. E. (1996), “Star arboricity of graphs”, Discrete Math. 149 : 93–98, doi :10.1016/0012-365X(94)00313-8 ^ Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004), “Star coloring of graphs”, Journal of Graph Theory 47 (3): 163–182, doi :10.1002/jgt.20029 ^ Robertson, Neil ; Seymour, Paul D. (1991), “Graph minors. X. Obstructions to tree-decomposition”, Journal of Combinatorial Theory 52 (2): 153–190, doi :10.1016/0095-8956(91)90061-N ^ Linial, Nathan (2002), “Finite metric spaces–combinatorics, geometry and algorithms”, Proc. International Congress of Mathematicians, Beijing , 3 , pp. 573–586, arXiv :math/0304466
