特別な弦グラフ（下位分類）
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/05 07:45 UTC 版)
「弦グラフ」の記事における「特別な弦グラフ（下位分類）」の解説
区間グラフは道の部分木の交差グラフであり、木の特殊な場合である。したがって、弦グラフの一種である。 スプリットグラフは、あるグラフと、その補グラフがともに弦グラフであるようなグラフである。頂点数nが増加するにつれ、弦グラフがスプリットグラフである割合は1に近づくBender, Richmond & Wormald (1985). プトレマイオスグラフは、弦グラフの内、Distance-hereditary graphでもあるものをいう。Distance-hereditary graphとは、2頂点間の距離が、その2頂点を含む任意の連結な誘導部分グラフにおいても変化しないグラフである。準閾値グラフはプトレマイオスグラフの一種であり、弦グラフであり、cographであるプトレマイオスグラフをいう。 ブロックグラフもプトレマイオスグラフの一種であり、任意の2つの極大クリークが少なくとも1つの頂点を共有するようなグラフである。風車グラフはさらにそのブロックグラフの特殊な例であり、任意の2つの極大クリークの共有頂点がある1つの頂点であるようなグラフである。 強弦グラフ（英語版）はn-sun (n>=3)グラフを誘導部分グラフとして持たない弦グラフである。ここで、 n-sun グラフとは、2n頂点からなるハミルトン閉路に、奇数個離れた頂点をつなぐ弦が1個しか含まれないないグラフである。頂点集合内には隣接する頂点が1組ずつしかないような2つの頂点集合に分けられるグラフでもある（その場合、閉路に対して奇数個目と偶数個目の頂点の集合となる。）。 K-木は全ての極大クリークと極大クリーク分離が同じサイズの弦グラフである。アポロニアンネットワークは、弦グラフである極大平面グラフもしくは平面グラフである3-木である。 極大外平面グラフは2-木のサブクラスであり、そのため弦グラフである。
※この「特別な弦グラフ（下位分類）」の解説は、「弦グラフ」の解説の一部です。
「特別な弦グラフ（下位分類）」を含む「弦グラフ」の記事については、「弦グラフ」の概要を参照ください。
- 特別な弦グラフのページへのリンク
