辺推移グラフ

曖昧さ回避 この項目では、グラフ理論について説明しています。幾何学における「辺推移的」については「en:Edge-transitive」をご覧ください。

数学のグラフ理論の分野における辺推移グラフ（へんすいいグラフ、英: edge-transitive graph）とは、与えられた任意の辺 e1 および e2 に対して、e1 を e2 へと写す自己同型（英語版）が存在するようなグラフ G のことを言う[1]。

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

例と性質

グレイグラフ（英語版）は辺推移的かつ正則であるが、頂点推移的ではない。

完全2部グラフ K m , n {\displaystyle K_{m,n}} や、対称グラフ（例えば立方体の頂点と辺から成るようなグラフ）は、どのようなものであっても辺推移グラフである[1]。対称グラフは（連結であれば）頂点推移的であるが、一般的に、辺推移グラフが頂点推移的であるとは限らない。グレイグラフ（英語版）はそのように辺推移的であるが頂点推移的でないグラフの例である。そのようなグラフは全て2部グラフであり[1]、したがって2色のみを使って彩色することが出来る。

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

関連項目

  • 辺推移的 (幾何学)（英語版）

参考文献

  1. ^ a b c Biggs, Norman (1993). Algebraic Graph Theory (2nd ed. ed.). Cambridge: Cambridge University Press. p. 118. ISBN 0-521-45897-8 
  2. ^ Lauri, Josef; Scapellato, Raffaele (2003), Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Student Texts, Cambridge University Press, pp. 20–21, ISBN 9780521529037, https://books.google.co.jp/books?id=hsymFm0E0uIC&pg=PA20&redir_esc=y&hl=ja .

外部リンク

  • Weisstein, Eric W. "Edge-transitive graph". mathworld.wolfram.com (英語).