バーレカンプ-ヴァン・リント-ザイデルグラフのソースを表示

[[File:The Berlekamp-van Lint-Seidel Graph.png|thumb|460x460px|バーレカンプ–ヴァン・リント–ザイデルグラフの2通りの描像]][[グラフ理論]]において、'''バーレカンプ–ヴァン・リント–ザイデルグラフ'''（{{Lang-en-short|Berlekamp–van Lint–Seidel graph}}）は{{仮リンク|局所線形グラフ|label=局所線形|en|locally linear graph}}[[強正則グラフ]]でパラメータ (243,22,1,2) を持つものである。つまり、[[頂点 (グラフ理論)|頂点]]が243個で、どの頂点にも22本の辺が接続し（辺は総計すると2673本になる）、どの隣接する2頂点も共通するちょうど1個の頂点と隣接し、どの隣接しない2頂点も共通するちょうど2個の頂点と隣接する。[[エルウィン・バーレカンプ]]、{{仮リンク|J・H・ヴァン・リント|en|J. H. van Lint}}、{{仮リンク|ヨハン・ヤコブ・ザイデル|de|Johan Jacob Seidel|nl|Jaap Seidel}}によって、[[ゴレイ符号]]の{{仮リンク|シュライアーコセットグラフ|en|Schreier coset graph}}として構成された{{r|bvls}}。

このグラフは[[アーベル群]]の[[ケイリーグラフ]]である。アーベル的ケイリーグラフの中で、強正則グラフの最後の2個のパラメータがちょうど1だけ異なるものは、{{仮リンク|ペイリーグラフ|en|Paley graph}}を除けばこのグラフのみである{{r|ajmp}}。これは{{仮リンク|整数グラフ|en|integral graph}}、つまり[[隣接行列]]の[[固有値]]が全て整数となるグラフでもある{{r|mw}}。また <math>9\times 9</math> の{{仮リンク|数独グラフ|en|Sudoku graph}}と同じく、整数的なアーベル的ケイリーグラフで、全ての元の[[位数 (群論)|位数]]が3である（3はそのようなグラフが存在できるような小さな数のうちの一つ）{{r|ks}}。

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

==関連項目==
*[[:en:Games graph]]

==脚注==
{{reflist|refs=

<ref name=ajmp>{{citation
 | last1 = Arasu | first1 = K. T.
 | last2 = Jungnickel | first2 = D. | author2-link = Dieter Jungnickel 
 | last3 = Ma | first3 = S. L.
 | last4 = Pott | first4 = A.
 | doi = 10.1016/0097-3165(94)90007-8
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 1280602
 | pages = 116–125
 | series = Series A
 | title = Strongly regular Cayley graphs with <math>\lambda-\mu=-1</math>
 | volume = 67
 | year = 1994}}</ref>

<ref name=con>{{citation
 | last = Conway | first = John H. | author-link = John Horton Conway
 | accessdate = 2019-02-12
 | publisher = Online Encyclopedia of Integer Sequences
 | title = Five $1,000 Problems (Update 2017)
 | url = https://oeis.org/A248380/a248380.pdf}}</ref>

<ref name=bvls>{{citation
 | last1 = Berlekamp | first1 = E. R. | author1-link = Elwyn Berlekamp
 | last2 = van Lint | first2 = J. H. | author2-link = J. H. van Lint
 | last3 = Seidel | first3 = J. J.
 | doi = 10.1016/B978-0-7204-2262-7.50008-9
 | journal = A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971)
 | mr = 0364015
 | pages = 25–30
 | publisher = North-Holland | location = Amsterdam
 | title = A strongly regular graph derived from the perfect ternary Golay code
 | year = 1973}}</ref>

<ref name=ks>{{citation
 | last1 = Klotz | first1 = Walter
 | last2 = Sander | first2 = Torsten
 | issue = 1
 | journal = Electronic Journal of Combinatorics
 | mr = 2651734
 | page = Research Paper 81, 13pp
 | title = Integral Cayley graphs over abelian groups
 | url = https://www.combinatorics.org/Volume_17/Abstracts/v17i1r81.html
 | volume = 17
 | year = 2010}}</ref>

<ref name=mm>{{citation
 | last1 = Makhnev | first1 = A. A.
 | last2 = Minakova | first2 = I. M.
 | date = January 2004
 | doi = 10.1515/156939204872374
 | issue = 2
 | journal = Discrete Mathematics and Applications
 | mr = 2069991
 | title = On automorphisms of strongly regular graphs with parameters <math>\lambda=1</math>, <math>\mu=2</math>
 | volume = 14}}</ref>

<ref name=mw>{{mathworld|title=Berlekamp-van Lint-Seidel Graph|id=Berlekamp-vanLint-SeidelGraph}}</ref>

}}

{{DEFAULTSORT:はあれかんふうあんりんとさいてるくらふ}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]