バーレカンプ-ヴァン・リント-ザイデルグラフ

提供: testwiki
ナビゲーションに移動 検索に移動
バーレカンプ–ヴァン・リント–ザイデルグラフの2通りの描像

グラフ理論において、バーレカンプ–ヴァン・リント–ザイデルグラフテンプレート:Lang-en-short)はテンプレート:仮リンク強正則グラフでパラメータ (243,22,1,2) を持つものである。つまり、頂点が243個で、どの頂点にも22本の辺が接続し(辺は総計すると2673本になる)、どの隣接する2頂点も共通するちょうど1個の頂点と隣接し、どの隣接しない2頂点も共通するちょうど2個の頂点と隣接する。エルウィン・バーレカンプテンプレート:仮リンクテンプレート:仮リンクによって、ゴレイ符号テンプレート:仮リンクとして構成されたテンプレート:R

このグラフはアーベル群ケイリーグラフである。アーベル的ケイリーグラフの中で、強正則グラフの最後の2個のパラメータがちょうど1だけ異なるものは、テンプレート:仮リンクを除けばこのグラフのみであるテンプレート:R。これはテンプレート:仮リンク、つまり隣接行列固有値が全て整数となるグラフでもあるテンプレート:R。また 9×9テンプレート:仮リンクと同じく、整数的なアーベル的ケイリーグラフで、全ての元の位数が3である(3はそのようなグラフが存在できるような小さな数のうちの一つ)テンプレート:R

どの隣接する2頂点も共通するちょうど1個の頂点と隣接し、どの隣接しない2頂点も共通するちょうど2個の頂点と隣接するような強正則グラフのパラメータがとり得る組み合わせは5通りある。これらのうち、2通りは存在することが知られていて、バーレカンプ–ヴァン・リント–ザイデルグラフと9頂点のペイリーグラフ(パラメータ (9,4,1,2))であるテンプレート:Rコンウェイの99グラフ問題はこれら以外の、パラメータ (99,14,1,2) のグラフが存在するかどうかを問うものであるテンプレート:R

関連項目

脚注

テンプレート:Reflist