About: 半対称グラフ

数学のグラフ理論の分野における半対称グラフ（はんたいしょうグラフ、英: semi-symmetric graph）とは、辺推移的かつ正則であるが、頂点推移的でない無向グラフのことを言う。 言い換えると、グラフが半対称的であるとは、各頂点に接続する辺の数が等しく、各辺を別のどの辺へも推移することの出来る対称性が存在するが、ある頂点のペアに対しては、対称性によってそれらを別のものへと推移することが出来ないことを言う。半対称グラフは2部グラフであり、そのは bipartition の各二頂点の集合上で推移的に作用する。右上図において、緑の頂点はどのような自己同型によっても赤い頂点へ写されることはない。 半対称グラフは、1967年、最小の半対称グラフである 20 頂点のフォークマングラフを発見したによって初めて研究された 。 最小の立方体半対称グラフは、54 頂点のである。そのグラフが半対称であることは によって初めて確認された。また、最小の立方体半対称グラフであることは、とアレクサンダー・マルニッチによって証明された。