半対称グラフ

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

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

半対称グラフは、1967年、最小の半対称グラフである 20 頂点のフォークマングラフを発見したによって初めて研究された 。

最小の立方体半対称グラフは、54 頂点のである。そのグラフが半対称であることは  によって初めて確認された。また、最小の立方体半対称グラフであることは、とアレクサンダー・マルニッチによって証明された。

立方体半対称グラフについては、768 頂点のものまでが知られている。コンダー、マルニッチ、マルシッチおよびポトチェニクによれば、グレイグラフに続く最小の四つの立方体半対称グラフには、110 頂点のイオフィノヴァ-イヴァノフグラフ、112 頂点の、120 頂点の内周 8 のグラフ、およびがある。

参考文献

外部リンク 

グラフ理論のグラフ
数学に関する記事
代数的グラフ理論