会議グラフ

数学における未解決問題

頂点の数ごとに会議グラフは存在するか？${\displaystyle v>1}$どこ${\displaystyle v\equiv 1{\bmod {4}}}$そして${\displaystyle v}$2つの平方数の和は奇数ですか？

数学における未解決問題

グラフ理論の数学分野では、会議グラフは、パラメータv、k = ( v − 1)/2、λ = ( v − 5)/4、 μ = ( v − 1)/4 を持つ強正則グラフです。これは対称会議行列 に関連付けられたグラフであり、したがってその次数vは (4 を法として) 1 でなければならず、 2 つの平方数の和でなければなりません。^{[ 1 ]}

制約によって許容されるすべての小さなvの値、例えばv = 5、9、13、17、25、29、および ( Paley グラフ) 1 に合同なすべての素数のべき乗 (mod 4) に対して、会議グラフが存在することが知られています。しかし、会議グラフの存在が不明な許容されるvの値は多数あります。Paleyグラフは存在しないが会議グラフが存在する最小のvの値は、1978 年に発見されたv = 45です。 ^{[ 2 ]}次に小さいv = 65 は、40 年以上後の 2021 年に発見されました。^{[ 3 ] [ 4 ]}現在、最小の未解決ケースはv = 85です。 ^{[ 4 ]}

会議グラフの固有値は、他の強正則グラフとは異なり、整数である必要はありません。グラフが連結である場合、固有値は重複度 1 のkと、他の 2 つの固有値、

${\displaystyle {\frac {-1\pm {\sqrt {v}}}{2}},}$

それぞれ重複度は( v − 1)/2 である。

会議グラフの補グラフは常に同じパラメータを持つ会議グラフであり、多くの場合、自己補グラフとなる。例えば、すべてのペイリーグラフがそうである。

• （ OEISのシーケンスA057653）、2乗の和である奇数
• （OEISのシーケンスA085759）、4n+1の形の素数のべき乗。