ヒーウッドグラフ

ヒーウッドグラフ

ヒーウッドグラフは、数学におけるグラフ理論の中で重要な役割を果たす無向グラフです。このグラフは、14個の頂点と21本の辺から構成され、イギリスの数学者パーシー・ジョン・ヒーウッドに由来します。ヒーウッドグラフの特性や構造は、組合せ、幾何、代数の観点から多くの研究が行われており、特に6-ケージとして知られる性質に注目されています。

組合せの性質

ヒーウッドグラフは立方体の性質を持ち、すべての閉路は6本以上の辺を含んでいます。これは他の立方体グラフとは異なり、短い閉路を持たないことから、ヒーウッドグラフ自体が最小の6-ケージであることを意味します。このグラフは距離推移グラフでもあり、距離正則です。さらに、24の完全マッチングが存在し、各マッチングの欠けた辺で形成される集合はハミルトン閉路を構成します。適切な方法を用いることで、ヒーウッドグラフを三つの完全マッチングに分けることができ、そこには八通りの組み合わせがあります。

ヒーウッドグラフには28の6-閉路が含まれており、各6-閉路は互いに素であり、対称差によって他の6-閉路との関係が成り立ちます。これにより、ヒーウッドグラフには六つの互いに近接した領域を形作る細分割が存在します。

幾何および位相的性質

ヒーウッドグラフはトロイダルグラフでもあり、トーラス上に交錯することなく埋め込むことが可能です。この埋め込みの一例は、三次元ユークリッド空間内の非凸多面体として表現されることが多いです。ヒーウッドの名前の由来は、1890年に彼が示した多角形の7色定理に関連しています。これによって、ヒーウッドグラフは7色で彩色できるという性質を持つことが明示されています。

また、ヒーウッドグラフはファノ平面のレヴィグラフとしても機能し、幾何学的な点と距離の関係を表す役割も果たしています。これにより、ヒーウッドグラフに見られる6-閉路はファノ平面における三角形に対応します。さらに、交差数が3であるため、立方体グラフの中では最小の交差数を持つグラフとしても知られています。

代数的性質

ヒーウッドグラフは、自己同型群が位数336の射影線型群PGL2(7)と同型であるため、非常に対称的なグラフです。任意の頂点や辺は互いに移動できる自己同型を持っており、これはヒーウッドグラフが唯一の立方体対称グラフであることを示しています。

グラフの固有多項式は、特有の特徴を持ち、次のような形式で表されます。

$$
(x-3)(x+3)(x^2-2)^6
$$

この結論から、ヒーウッドグラフはこの固有多項式を持つ唯一のグラフであり、スペクトルによってその特性が決定される重要な対象であると言えます。

ギャラリー

(ここにヒーウッドグラフの視覚的な資料や図が入ります)

参考文献

(ここに関連する参考文献や資料が入ります)

もう一度検索