スター（グラフ理論）

星
星
	星S 7。(一部の著者はこれをS 8として索引付けしています。)
頂点	1 ...
エッジ	け
直径	2
胴回り	∞
彩度数	2
色指数	け
プロパティ	エッジ推移; ツリー; 単位距離; 二部
表記	S k
	グラフとパラメータの表

グラフ理論において、スター $S k$ は完全な二部グラフ $K 1, k 、$ すなわち1 つの内部ノードと $k 個$ の葉を持つ木(ただし、 $k$ $\leq 1$ の場合は内部ノードはなく、 $k$ $+ 1$ 個の葉) です。あるいは、一部の著者は $S$ $k を$ 最大直径2 の順序 $k$ の木と定義します。この場合、 $k$ $> 2のスターには$ $k$ $- 1 個の$ 葉があります。

3 つの辺を持つ星は、爪と呼ばれます。

星 $S k は$ $、 k$ が偶数のときは辺優美ですが、 $k$ が奇数のときは辺優美ではありません。これは辺推移的なマッチ棒グラフであり、直径 2 ( $l$ $> 1$ のとき)、内周∞ (閉路はありません)、彩色指数 $k$ 、彩色数2 ( $k$ $> 0$ のとき) を持ちます。さらに、星には大きな自己同型群、つまり $k$ 文字上の対称群があります。

スターは、最大でも 1 つの頂点の次数が1 より大きい唯一の連結グラフとも言えます。

他のグラフファミリーとの関係

クローは、クローを誘導部分グラフとして持たないグラフであるクローフリーグラフの定義で注目される。^[1]^{[2]また、これらは}ホイットニーグラフ同型定理の例外的なケースの1つでもある。一般に、同型線グラフを持つグラフは、クローと三角形 $K$ $3$ を除いて、それ自体が同型である。^[3]

星は特別な種類の木です。他の木と同様に、星はプリューファーシーケンスでエンコードされます。星 $K 1, k$ $のプリューファーシーケンスは、中心頂点のk - 1個$ のコピーで構成されます。^[4]

いくつかのグラフ不変量はスターの観点から定義されます。スター樹状度は、各フォレスト内の各ツリーがスターになるようにグラフを分割できるフォレストの最小数です。^[5]また、グラフのスター彩度数は、2 つの色クラスが一緒になってすべての接続コンポーネントがスターであるサブグラフを形成するように頂点を着色するために必要な色の最小数です。^[6]枝幅1のグラフは、各接続コンポーネントがスターであるグラフです。^[7]

その他のアプリケーション

爪の頂点間の距離の集合は、任意の次元のユークリッド空間に等長的に埋め込むことができない有限距離空間の例を提供します。 ^[8]

スターグラフをモデルにしたコンピュータネットワークであるスターネットワークは、分散コンピューティングにおいて重要です。

スターグラフの幾何学的実現は、ある固定長の間隔でエッジを識別することによって形成され、熱帯幾何学における曲線の局所モデルとして使用されます。熱帯曲線は、星形の計量グラフに局所的に同型である計量空間として定義されます。

参照

スター (単体複体) - グラフから任意の単体複体へのスターの概念の一般化。

参考文献

^ フォードリー、ラルフ; フランドリン、エヴェリン; リャチェク、ズデニェク (1997)、「クローフリーグラフ - 概観」、離散数学、164 (1–3): 87–147、doi : 10.1016/S0012-365X(96)00045-3、MR 1432221。
^ チュドノフスキー、マリア、シーモア、ポール(2005)、「クローフリーグラフの構造」、組合せ論調査 2005 (PDF)、ロンドン数学協会講義ノートシリーズ、第 327 巻、ケンブリッジ: ケンブリッジ大学出版局、pp. 153–171、MR 2187738。
^ ホイットニー、ハスラー（1932年1月）、「同型グラフとグラフの連結性」、アメリカ数学誌、54（1）：150–168、doi：10.2307/2371086、hdl：10338.dmlcz/101067、JSTOR 2371086。
^ Gottlieb, J.; Julstrom, BA; Rothlauf, F.; Raidl, GR (2001)、「Prüfer 数: 進化的探索におけるスパニングツリーの不適切な表現」(PDF)、GECCO-2001: Proceedings of the Genetic and Evolutionary Computation Conference、Morgan Kaufmann、pp. 343–350、ISBN 1558607749、 2006-09-26にオリジナル（PDF）からアーカイブ
^ Hakimi, SL; Mitchem, J.; Schmeichel, EE (1996)、「グラフのスター樹状性」、Discrete Math.、149 (1–3): 93–98、doi : 10.1016/0012-365X(94)00313-8
^ Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004)、「グラフのスターカラーリング」、Journal of Graph Theory、47 (3): 163–182、doi :10.1002/jgt.20029。
^ ロバートソン、ニール;シーモア、ポール D. (1991)、「グラフマイナー。X.ツリー分解の障害」、組み合わせ理論ジャーナル、52 (2): 153–190、doi : 10.1016/0095-8956(91)90061-N。
^ Linial, Nathan (2002)、「有限距離空間 - 組合せ論、幾何学、アルゴリズム」、国際数学者会議論文集、北京、第 3 巻、pp. 573-586、arXiv : math/0304466、Bibcode :2003math......4466L

[1] フォードリー、ラルフ; フランドリン、エヴェリン; リャチェク、ズデニェク (1997)、「クローフリーグラフ - 概観」、離散数学、164 (1–3): 87–147、doi : 10.1016/S0012-365X(96)00045-3、MR 1432221。

[2] チュドノフスキー、マリア、シーモア、ポール(2005)、「クローフリーグラフの構造」、組合せ論調査 2005 (PDF)、ロンドン数学協会講義ノートシリーズ、第 327 巻、ケンブリッジ: ケンブリッジ大学出版局、pp. 153–171、MR 2187738。

[3] ホイットニー、ハスラー（1932年1月）、「同型グラフとグラフの連結性」、アメリカ数学誌、54（1）：150–168、doi：10.2307/2371086、hdl：10338.dmlcz/101067、JSTOR 2371086。

[4] Gottlieb, J.; Julstrom, BA; Rothlauf, F.; Raidl, GR (2001)、「Prüfer 数: 進化的探索におけるスパニングツリーの不適切な表現」(PDF)、GECCO-2001: Proceedings of the Genetic and Evolutionary Computation Conference、Morgan Kaufmann、pp. 343–350、ISBN 1558607749、 2006-09-26にオリジナル（PDF）からアーカイブ

[5] Hakimi, SL; Mitchem, J.; Schmeichel, EE (1996)、「グラフのスター樹状性」、Discrete Math.、149 (1–3): 93–98、doi : 10.1016/0012-365X(94)00313-8

[6] Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004)、「グラフのスターカラーリング」、Journal of Graph Theory、47 (3): 163–182、doi :10.1002/jgt.20029。

[7] ロバートソン、ニール;シーモア、ポール D. (1991)、「グラフマイナー。X.ツリー分解の障害」、組み合わせ理論ジャーナル、52 (2): 153–190、doi : 10.1016/0095-8956(91)90061-N。

[8] Linial, Nathan (2002)、「有限距離空間 - 組合せ論、幾何学、アルゴリズム」、国際数学者会議論文集、北京、第 3 巻、pp. 573-586、arXiv : math/0304466、Bibcode :2003math......4466L