デイターグラフ
| デイターグラフ | |
|---|---|
 | |
| 頂点 | 112 |
| エッジ | 336 |
| 半径 | 7 |
| 直径 | 7 |
| 胴回り | 4 |
| 自己同型 | 2688 |
| グラフとパラメータの表 | |
数学のグラフ理論の分野では、デイターグラフは112の頂点と336の辺を持つ6正則グラフである。[ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ]デイターグラフは、2進7立方体から長さ7のハミングコードのコピーを削除することによって得られる。
デイターグラフ、そして拡張して長さ2 r -1のハミングコードを(2 r -1)立方体から削除することによって得られるグラフは、対称グラフである。特に、デイターグラフは、正則次数3の半対称立方グラフの中で3番目に小さい、リュブリャナグラフの2つのコピーに3因数分解することができる。リュブリャナグラフの内周は10である 。
実際、Dejter グラフは、例えば右上の図のように {red, blue} の 2 色にできることが証明されています。その結果得られる、辺が単色の赤と青の頂点スパニング サブグラフはどちらも、リュブリャナ グラフのコピーになります。これらの 2 つのコピーには、Dejter グラフの 112 個の頂点とそれぞれ 168 個の辺が含まれており、両方のコピーの内周は 10 です。一方、Dejter グラフの内周は 6、7 立方体の内周は 4 です。Dejter グラフは、連結された自己補頂点スパニング半対称立方体サブグラフを持つ最小の対称グラフであると思われます。
デイターグラフの赤と青の頂点全域リュブリャナ部分グラフはどちらも、ヒーウッドグラフの被覆グラフ、すなわちヒーウッドグラフの8被覆として表すことができます。リュブリャナグラフの2つの表現（上が赤、下が青、両方とも右側）のそれぞれにおいて、ヒーウッドグラフの連続する頂点の反転像を交互に、例えば白黒（図を拡大するには画像を2回クリックすると見やすくなります）で着色することで、このことが示されています。これはヒーウッドグラフの二分割に基づいています。このような逆像はそれぞれ、7 次元立方体の固定座標方向に沿った、固定の重み 0 または 1 を持つハミング コードの半分の 8 つの近傍によって形成されます。これらの重みを順列 (0 1) によって交換することで、赤いリュブリャナ グラフによって提供される隣接関係から青いリュブリャナ グラフによって提供される隣接関係に移行したり、その逆を行ったりすることができます。
Dejter グラフの 7 分の 1 は、下の別の図に表示され、Heawood グラフの 2 つの結果のコピーから取得できます。
参考文献
- ^ Klin M.; Lauri J.; Ziv-Av M.「112頂点上の2つの半対称グラフ間のリンク：アソシエーションスキームのレンズを通して」、Jour. Symbolic Comput.、47–10、2012年、1175–1191。
- ^ Borges J.; Dejter IJ「超立方体とその補集合における完全支配集合について」、J. Combin. Math. Combin. Comput. 20 (1996), 161-173
- ^ Dejter IJ「7次元立方体の対称部分グラフについて：概要」、離散数学124（1994）55–66
- ^ Dejter IJ「7-cube Hamming shell の因子の対称性」、J. Combin. Des. 5 (1997)、301–309
- ^ Dejter IJ; Guan P.「超立方体における正方形ブロッキング辺部分集合と頂点回避」、グラフ理論、組合せ論、アルゴリズム、および応用（サンフランシスコ、カリフォルニア州、1989年）、162–174ページ、SIAM、フィラデルフィア、ペンシルベニア州、1991年
- ^ Dejter IJ; Pujol J. 「ハイパーキューブにおける完全支配と対称性」、第26回南東部国際組合せ論・グラフ理論・計算会議（フロリダ州ボカラトン、1995年）議事録。Congr. Numer. 111 (1995), 18–32
- ^ Dejter IJ; Weichsel PM「超立方体のねじれ完全支配部分グラフ」、第24回南東部国際組合せ論・グラフ理論・計算会議（フロリダ州ボカラトン、1993年）議事録。Congr. Numer. 94 (1993), 67–78
