| M 22グラフ、メスナーグラフ[1] [2] [3] | |
|---|---|
 | |
| 名前の由来 | マシュー・グループ M 22、デイル・M・メスナー |
| 頂点 | 77 |
| エッジ | 616 |
| グラフとパラメータの表 | |
M 22グラフはメスナーグラフまたはウィットグラフとも呼ばれ、[1] [2] [3] [4]、パラメータ(77, 16, 0, 4) を持つ唯一の強正則グラフです。 [5]これはシュタイナーシステム(3, 6, 22) から、77 個のブロックを頂点として表し、共通の項を持たない 2 つの頂点を結合するか、ヒグマン・シムズグラフから頂点とその隣接頂点を削除することによって構築されます。[6] [7]
任意の項について、その項を含むブロックの族は、このグラフにおいて21個の頂点を持つ独立集合を形成する。エルデシュ・コー・ラド定理（クネーザーグラフの独立集合を用いて定式化できる）に類似した結果、これらはこのグラフにおける唯一の最大独立集合となる。 [4]
これは7つの既知の三角形のない強正則グラフのうちの1つである。[8] そのグラフスペクトルは(−6)21255161、[ 6 ]であり、その自己同型群はマシュー群M22である。[5]
参照
参考文献
- ^ ab 「パラメータ(77,16,0,4)を持つメスナーグラフ。自己同型群の位数は887040であり、NL2(10)の自己同型群の点の安定群と同型である。」
- ^ ab スライド5の三角形のないSRGのリストには「メスナーグラフ」と記載されています
- ^ ab セクション 3.2.6 メスナーグラフ
- ^ ab Godsil, Christopher ; Meagher, Karen (2015)、「Section 5.4: The Witt graph」、Erdős–Ko–Rado Theorems: Algebraic Approaches、Cambridge Studies in Advanced Mathematics、Cambridge University Press、pp. 94– 96、ISBN 9781107128446
- ^ ab Brouwer、Andries E.「M 22グラフ」。アイントホーフェン工科大学、http://www.win.tue.nl/~aeb/graphs/M22.html。 2018 年 5 月 29 日にアクセス。
- ^ ab Weisstein, Eric W. “M22 Graph.” MathWorld, http://mathworld.wolfram.com/M22Graph.html. 2018年5月29日にアクセス。
- ^ Vis, Timothy. 「Higman–Simsグラフ」コロラド大学デンバー校、http://math.ucdenver.edu/~wcherowi/courses/m6023/tim.pdf。2018年5月29日にアクセス。
- ^ Weisstein, Eric W. 「Strongly Regular Graph」 Wolfram MathWorld より、mathworld.wolfram.com/StronglyRegularGraph.html。
外部リンク
- MathWorldのM22グラフ
