数学のグラフ理論の分野における辺推移グラフ（へんすいいグラフ、）とは、与えられた任意の辺 e1 および e2 に対して、e1 を e2 へと写すが存在するようなグラフ G のことを言う。

言い換えると、グラフが辺推移的であるとは、その自己同型群が各辺の上で推移的に作用することを言う。

例と性質

完全2部グラフ や、対称グラフ（例えば立方体の頂点と辺から成るようなグラフ）は、どのようなものであっても辺推移グラフである。対称グラフは（連結であれば）頂点推移的であるが、一般的に、辺推移グラフが頂点推移的であるとは限らない。はそのように辺推移的であるが頂点推移的でないグラフの例である。そのようなグラフは全て2部グラフであり、したがって2色のみを使って彩色することが出来る。

正則であるが頂点推移的でないような辺推移グラフは、半対称グラフと呼ばれる。そのような例として、が再び挙げられる。すべての辺推移グラフは必ず2部グラフであり、また、半対称であるかであるかのいずれかである.。

関連項目

参考文献

外部リンク