半対称グラフとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 半対称グラフの意味・解説 

半対称グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/01/24 09:54 UTC 版)

ナビゲーションに移動 検索に移動
フォークマングラフは最小の半対称グラフである。

数学グラフ理論の分野における半対称グラフ(はんたいしょうグラフ、: 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 .

外部リンク




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「半対称グラフ」の関連用語

半対称グラフのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



半対称グラフのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの半対称グラフ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS