半対称グラフ

フォークマングラフは最小の半対称グラフである。

数学のグラフ理論の分野における半対称グラフ（はんたいしょうグラフ、英: semi-symmetric graph）とは、辺推移的かつ正則であるが、頂点推移的でない無向グラフのことを言う。

言い換えると、グラフが半対称的であるとは、各頂点に接続する辺の数が等しく、各辺を別のどの辺へも推移することの出来る対称性が存在するが、ある頂点のペアに対しては、対称性によってそれらを別のものへと推移することが出来ないことを言う。半対称グラフは2部グラフであり、その自己同型群（英語版）は bipartition の各二頂点の集合上で推移的に作用する。右上図において、緑の頂点はどのような自己同型によっても赤い頂点へ写されることはない。

半対称グラフは、1967年、最小の半対称グラフである 20 頂点のフォークマングラフを発見したジョン・フォークマン（英語版）によって初めて研究された[1] 。

最小の立方体半対称グラフは、54 頂点のグレイグラフ（英語版）である。そのグラフが半対称であることは Bouwer (1968) によって初めて確認された。また、最小の立方体半対称グラフであることは、ドラガン・マルシッチ（英語版）とアレクサンダー・マルニッチによって証明された[2]。

立方体半対称グラフについては、768 頂点のものまでが知られている。コンダー、マルニッチ、マルシッチおよびポトチェニクによれば、グレイグラフに続く最小の四つの立方体半対称グラフには、110 頂点のイオフィノヴァ-イヴァノフグラフ、112 頂点のリュブリャナグラフ（英語版）[3]、120 頂点の内周 8 のグラフ、およびトゥッテ-12ケージ（英語版）がある[4]。

参考文献

  1. ^ Folkman, J. (1967), “Regular line-symmetric graphs”, Journal of Combinatorial Theory 3 (3): 215–232, doi:10.1016/S0021-9800(67)80069-3 .
  2. ^ Bouwer, I. Z. (1968), “An edge but not vertex transitive cubic graph”, Bulletin of the Canadian Mathematical Society 11: 533–535, doi:10.4153/CMB-1968-063-0 .
  3. ^ Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; Potočnik, P. (2002), “The Ljubljana Graph”, IMFM Preprints (Ljubljana: Institute of Mathematics, Physics and Mechanics) 40 (845), http://www.imfm.si/preprinti/PDF/00845.pdf .
  4. ^ Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Potočnik, Primož (2006), “A census of semisymmetric cubic graphs on up to 768 vertices”, Journal of Algebraic Combinatorics 23 (3): 255–294, doi:10.1007/s10801-006-7397-3 .

外部リンク