半対称グラフ
数学のグラフ理論の分野における半対称グラフ（はんたいしょうグラフ、英: semi-symmetric graph）とは、辺推移的かつ正則であるが、頂点推移的でない無向グラフのことを言う。
言い換えると、グラフが半対称的であるとは、各頂点に接続する辺の数が等しく、各辺を別のどの辺へも推移することの出来る対称性が存在するが、ある頂点のペアに対しては、対称性によってそれらを別のものへと推移することが出来ないことを言う。半対称グラフは2部グラフであり、その自己同型群は bipartition の各二頂点の集合上で推移的に作用する。右上図において、緑の頂点はどのような自己同型によっても赤い頂点へ写されることはない。
半対称グラフは、1967年、最小の半対称グラフである 20 頂点のフォークマングラフを発見したジョン・フォークマンによって初めて研究された[1] 。
最小の立方体半対称グラフは、54 頂点のグレイグラフである。そのグラフが半対称であることは Bouwer (1968) によって初めて確認された。また、最小の立方体半対称グラフであることは、ドラガン・マルシッチとアレクサンダー・マルニッチによって証明された[2]。
立方体半対称グラフについては、768 頂点のものまでが知られている。コンダー、マルニッチ、マルシッチおよびポトチェニクによれば、グレイグラフに続く最小の四つの立方体半対称グラフには、110 頂点のイオフィノヴァ-イヴァノフグラフ、112 頂点のリュブリャナグラフ[3]、120 頂点の内周 8 のグラフ、およびトゥッテ-12ケージがある[4]。
参考文献 編集
- ^ Folkman, J. (1967), “Regular line-symmetric graphs”, Journal of Combinatorial Theory 3 (3): 215–232, doi:10.1016/S0021-9800(67)80069-3.
- ^ 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.
- ^ 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).
- ^ 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.
外部リンク 編集
- Weisstein, Eric W. "Semisymmetric Graph". mathworld.wolfram.com (英語).