エッジ推移グラフ

数学のグラフ理論の分野において、 辺推移グラフとは、G の任意の2つの辺e ₁とe _{2 が}与えられたときに、 e _{1 を}e ₂に写像するGの自己同型が存在するようなグラフGのことである。^[1]

言い換えれば、自己同型群がグラフのエッジに対して 推移的に作用する場合、そのグラフはエッジ推移的であると言えます。

n 頂点に接続された単純な辺推移グラフの数は 1、1、2、3、4、6、5、8、9、13、7、19、10、16、25、26、12、28 ... です ( OEISのシーケンスA095424 )

辺推移グラフには、立方体の頂点や辺など、すべての対称グラフが含まれます。^[1] 対称グラフも頂点推移的です(接続されている場合は) が、一般に辺推移グラフは頂点推移である必要はありません。頂点推移的でないすべての接続された辺推移グラフは、二部グラフでなければならず^[1] (したがって、 2色のみで色付けできます)、半対称グラフまたは双正則グラフのいずれかです。^[2]

辺は推移的だが頂点は推移的ではないグラフの例には、 m ≠ n である完全二部グラフ があり、これにはスターグラフが含まれます。 n 頂点のグラフの場合、奇数 n に対して (n-1)/2 個のグラフがあり、偶数 n に対して (n-2) 個のグラフがあります。 対称ではない追加の辺推移グラフは、特定のケースではこれらの完全二部グラフのサブグラフとして形成されます。 完全二部グラフ K _m,nのサブグラフは、m と n が 2 より大きい因数を共有する場合に存在します。 最大公約数が 2 の場合、2n/m が偶数の場合、または m=4 で n が 6 の奇数倍の場合にサブグラフが存在します。 ^{[3]そのため、辺推移サブグラフは K} _3,6、 K _4,6、および K _5,10に対して存在しますが、 K _4,10に対しては存在しません。いくつかの辺推移グラフの代替構築法は、v 個の頂点と e 個の辺を持つ対称グラフの辺の中点に頂点を追加し、e 個の頂点の順序が 2、v の順序が 2e/v の二部グラフを作成することです。 ${\displaystyle K_{m,n}}$${\displaystyle K_{1,n}}$

辺推移グラフであり、正則グラフでもあるが、頂点推移グラフではないグラフは、半対称グラフと呼ばれます。54個の頂点を持つ立方グラフであるグレイ グラフは、辺推移グラフであるが頂点推移グラフではない正則グラフの例です。20個の頂点を持つ四次グラフであるフォークマン グラフは、そのようなグラフの中で最小のものです。

辺推移グラフの頂点の接続性は常にその最小次数に等しい。^[4]

• エッジ推移（幾何学）

• Weisstein、Eric W.「エッジ推移グラフ」。MathWorld。