バーレカンプ-ヴァン・リント-ザイデルグラフとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > バーレカンプ-ヴァン・リント-ザイデルグラフの意味・解説 

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

(バーレカンプ–ヴァン・リント–ザイデルグラフ から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/06/23 08:13 UTC 版)

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

グラフ理論において、バーレカンプ–ヴァン・リント–ザイデルグラフ: Berlekamp–van Lint–Seidel graph)は局所線形英語版強正則グラフでパラメータ (243,22,1,2) を持つものである。つまり、頂点が243個で、どの頂点にも22本の辺が接続し(辺は総計すると2673本になる)、どの隣接する2頂点も共通するちょうど1個の頂点と隣接し、どの隣接しない2頂点も共通するちょうど2個の頂点と隣接する。エルウィン・バーレカンプ英語版J・H・ヴァン・リント英語版ヨハン・ヤコブ・ザイデルドイツ語版オランダ語版によって、ゴレイ符号シュライアーコセットグラフ英語版として構成された[1]

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

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

関連項目

脚注

  1. ^ Berlekamp, E. R.; van Lint, J. H.; Seidel, J. J. (1973), “A strongly regular graph derived from the perfect ternary Golay code”, A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (Amsterdam: North-Holland): 25–30, doi:10.1016/B978-0-7204-2262-7.50008-9, MR0364015 
  2. ^ Arasu, K. T.; Jungnickel, D.; Ma, S. L.; Pott, A. (1994), “Strongly regular Cayley graphs with ”, Journal of Combinatorial Theory, Series A 67 (1): 116–125, doi:10.1016/0097-3165(94)90007-8, MR 1280602 
  3. ^ Weisstein, Eric W. "Berlekamp-van Lint-Seidel Graph". MathWorld(英語).
  4. ^ Klotz, Walter; Sander, Torsten (2010), “Integral Cayley graphs over abelian groups”, Electronic Journal of Combinatorics 17 (1): Research Paper 81, 13pp, MR 2651734, https://www.combinatorics.org/Volume_17/Abstracts/v17i1r81.html 
  5. ^ Makhnev, A. A.; Minakova, I. M. (January 2004), “On automorphisms of strongly regular graphs with parameters , ”, Discrete Mathematics and Applications 14 (2), doi:10.1515/156939204872374, MR 2069991 
  6. ^ Conway, John H., Five $1,000 Problems (Update 2017), Online Encyclopedia of Integer Sequences, https://oeis.org/A248380/a248380.pdf 2019年2月12日閲覧。 



英和和英テキスト翻訳>> 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