Loading article…
グラフ理論において、ヘンソングラフ G i は無向無限グラフであり、 i頂点クリークを含まないが、すべてのK iフリー有限グラフを誘導サブグラフとして含む唯一の可算同次グラフです。たとえば、G 3 は三角形のないグラフであり、すべての有限三角形のないグラフが含まれています。
これらのグラフは、 1971年にこれらのグラフの構成法（すべてのi ≥ 3に対して）を発表したC. Ward Hensonにちなんで名付けられました。 [1]これらのグラフの最初のものG 3は、同次三角形フリーグラフまたは普遍三角形フリーグラフとも呼ばれます。
工事
これらのグラフを構築するために、ヘンソンはラドグラフの頂点を、頂点の有限集合Sごとに、 S を前の隣接頂点の集合として持つ頂点が無限に存在するという性質を持つシーケンスに順序付けます。(このようなシーケンスの存在は、ラドグラフを一意に定義します。) 次に、 G i を、ラドグラフのすべてのiクリークの最後の頂点 (シーケンス順序) を削除することによって形成されるラドグラフの誘導サブグラフとして定義します。 [1]
この構成では、各グラフG iはG i + 1の誘導サブグラフであり、この誘導サブグラフの連鎖の和集合が Rado グラフそのものです。各グラフG i はRado グラフの各iクリークから少なくとも 1 つの頂点を省略するため、 G iにはiクリークは存在できません。
普遍
任意の有限または可算なiクリークフリーグラフH は、一度に 1 頂点ずつ構築し、各ステップでG i内の以前の隣接頂点がH内の対応する頂点の以前の隣接頂点の集合と一致する頂点を追加することで、 G i の誘導サブグラフとして見つけることができます。つまり、G i はiクリークフリーグラフ のファミリのユニバーサルグラフです。
任意の大きな彩色数を持つiクリークフリーのグラフが存在するため、ヘンソングラフは無限の彩色数を持ちます。さらに強い言い方をすると、ヘンソングラフG i を任意の有限数の誘導サブグラフに分割すると、これらのサブグラフの少なくとも 1 つにiクリークフリーの有限グラフがすべて誘導サブグラフとして含まれます。[1]
対称
ラドーグラフと同様に、G 3には双方向ハミルトンパスが含まれており、パスの対称性はグラフ全体の対称性になります。ただし、 i > 3 のときのG iには当てはまりません。これらのグラフでは、グラフのすべての自己同型には複数の軌道があります。[1]
参考文献
- ^ abcd Henson, C. Ward (1971)、「可算同次グラフの族」、Pacific Journal of Mathematics、38 :69–83、doi : 10.2140/pjm.1971.38.69、MR 0304242。