他のグラフとの関係
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/07/04 11:55 UTC 版)
「スター (グラフ理論)」の記事における「他のグラフとの関係」の解説
頂点数が3のスターであるクローはクローフリーグラフ(部分グラフとしてクローを持たないグラフ)の定義で有名である。また、ハスラー・ホイットニー (Hassler Whitney) のグラフ同型定理(一般的に、グラフ同型な線グラフはクローと三角形グラフ K3を除き同型である。)の例外の1つでもある。 スターは木の特殊な場合であるため、木と同様にプリューファー列で表すことができ、スター Sk は中心の頂点を k-1 回並べた列となる。 スターの考え方を用いて定義されているグラフ不変量がいくつかある。スターの樹化数は森に含まれる木が全てスターとなるような分割を行った際の最小の森の数として定義されている。スター彩色数は、2つの色グループで彩色した場合、同じ色で接続された頂点グループが全てスターとなる彩色数である。分枝幅が1であるというのは、連結している分枝がそれぞれスターであることと同値である。
※この「他のグラフとの関係」の解説は、「スター (グラフ理論)」の解説の一部です。
「他のグラフとの関係」を含む「スター (グラフ理論)」の記事については、「スター (グラフ理論)」の概要を参照ください。
- 他のグラフとの関係のページへのリンク