半推移グラフ

自己同型によって定義されるグラフ族
距離推移	→	距離レギュラー	←	強く規則的な
↓
対称的（弧推移的）	←	t推移的、 t  ≥ 2		歪対称
↓
（接続されている場合） 頂点および辺が推移的	→	エッジ推移的かつ正則	→	エッジ推移的
↓		↓		↓
頂点推移	→	通常	→	（二部構成の場合） 双正則
↑
ケイリーグラフ	←	ゼロ対称		非対称

数学のグラフ理論の分野では、半推移グラフとは、頂点推移と辺推移の両方を備えているが、対称ではないグラフのことである。^[1] 言い換えれば、グラフの自己同型群が頂点と辺の両方に推移的に作用するが、連結された頂点の順序付きペアには作用しない場合、グラフは半推移的である。

ホルトグラフは最小の半推移グラフです。この図では鏡映対称性が欠如しているため、辺がその逆辺と等価ではないことが強調されています。

連結対称グラフはすべて頂点推移的かつ辺推移的であり、奇数次グラフではその逆が成り立つため^[2]、奇数次半推移グラフは存在しない。しかし、偶数次半推移グラフは存在する^[3] 。最小の半推移グラフはホルトグラフであり、次数は4、頂点数は27である^{[4 ]。 [5]}

参考文献

1. Gross, JL; Yellen, J. (2004).グラフ理論ハンドブック. CRC Press. p. 491. ISBN 1-58488-090-2。
2. Babai, L (1996). 「自己同型群、同型性、再構成」 Graham, R; Grötschel, M ; Lovász, L (編). Handbook of Combinatorics . Elsevier. 2010年6月11日時点のオリジナルよりアーカイブ。 2009年9月5日閲覧。
3. Bouwer, Z. (1970). 「頂点と辺は推移的だが、1-推移的ではないグラフ」. Canadian Mathematical Bulletin . 13 (2): 231– 237. doi : 10.4153/CMB-1970-047-8 .
4. ビッグス、ノーマン (1993).代数的グラフ理論（第2版）. ケンブリッジ: ケンブリッジ大学出版局. ISBN 0-521-45897-8。
5. Holt, Derek F. (1981). 「辺推移的だが弧推移的ではないグラフ」. Journal of Graph Theory . 5 (2): 201– 204. doi :10.1002/jgt.3190050210.。