| ホルトグラフ | |
|---|---|
 ホルト グラフでは、すべての頂点は同等であり、すべてのエッジも同等ですが、エッジはその逆とは同等ではありません。 | |
| 名前の由来 | デレク・F・ホルト |
| 頂点 | 27 |
| エッジ | 54 |
| 半径 | 3 |
| 直径 | 3 |
| 胴回り | 5 |
| 自己同型 | 54 |
| 彩色数 | 3 |
| 色指数 | 5 |
| 本の厚さ | 3 |
| キュー番号 | 3 |
| プロパティ | 頂点推移的、 辺推移的、 半推移的、 ハミルトン的 、オイラー的 、ケイリーグラフ |
| グラフとパラメータの表 | |
グラフ理論において、ホルトグラフまたはドイルグラフは最小の半推移グラフ、つまり対称でもない頂点推移かつ辺推移のグラフの最小の例である。[1] [2]このようなグラフは一般的ではない。[3]このグラフは、1976年[4]と1981年[5] にそれぞれ独立して同じグラフを発見したピーター・G・ドイルとデレク・F・ホルトにちなんで名付けられました。
ホルトグラフは、直径 3、半径3、周長 5、彩色数 3、彩色指数 5を持ち、98,472個の異なるハミルトン閉路を持つハミルトングラフである。 [6]また、4頂点連結、4辺連結のグラフでもある。本の厚さは3、待ち行列数は3である。 [7]
54位の自己同型群を持つ。[6]これは、同じ数の頂点と辺を持つ対称グラフが持つ群よりも小さい。右のグラフ図は、鏡映対称性を欠いていることから、この点を強調している。
ホルトグラフの特性多項式は
ギャラリー
参考文献
- ^ Doyle, P. 「頂点推移的かつ辺推移的だがL推移的ではない27頂点グラフ」1998年10月. [1]
- ^ アルスパッハ、ブライアン；マルシッチ、ドラガン；ノウィッツ、ルイス（1994）「1/2推移的なグラフの構築」オーストラリア数学会誌、シリーズA、56（3）：391–402、doi：10.1017/S1446788700035564。
- ^ ジョナサン・L・グロス、ジェイ・イエレン、『グラフ理論ハンドブック』、CRC Press、2004年、 ISBN 1-58488-090-2、491ページ。
- ^ Doyle, PG (1976)、「推移グラフについて」、ハーバード大学卒業論文. MathWorld により引用。
- ^ Holt, Derek F. (1981)、「辺推移的だが弧推移的ではないグラフ」、Journal of Graph Theory、5 (2): 201– 204、doi :10.1002/jgt.3190050210。
- ^ ab ワイスタイン、エリック W.「ドイル グラフ」。マスワールド。
- ^ ジェシカ・ウォルツ、「SATを用いた線形レイアウトのエンジニアリング」。修士論文、テュービンゲン大学、2018年
