Loading article…
数学のスペクトルグラフ理論の分野において、ブラウワー予想は、グラフの辺の数に関してラプラシアンの固有値の中間和の上限に関するアンドリース・ブラウワーの予想である。 [1]
この予想は、G が単純な無向グラフでL ( G ) がそのラプラシアン行列である場合、その固有値λ n ( L ( G )) ≤ λ n −1 ( L ( G )) ≤ ... ≤ λ 1 ( L ( G )) が次を満たすことを述べています 。 ここでm ( G ) はGの辺の数です。
最先端の
ブラウワーは計算によって、この予想が頂点数が最大10のグラフすべてに当てはまることを確認した。[1]また、 t = 1、2、n − 1、n の場合には、任意の数の頂点に対してもこの予想が当てはまることが知られている。
特定の種類のグラフでは、ブラウワー予想はすべてのtと任意の数の頂点に対して有効であることが知られています。特に、は木[2]と単巡回グラフおよび二巡回グラフに対して有効であることが知られています。[3]また、ブラウワー予想は 2 つの大きなグラフ ファミリに対して有効であることが証明されています。最初のグラフ ファミリは、クリークの各頂点を任意の c-巡回グラフの頂点と同一視することで得られるグラフであり、2 番目のファミリは、最大完全二部サブグラフの辺を削除することで、各非自明なコンポーネントが c-巡回グラフであるグラフが得られるグラフで構成されています。[4] ランダム グラフの特定のシーケンスでは、ブラウワー予想は、頂点の数が無限大に近づくにつれて確率が 1 に近づくことで有効になります。[5]
参考文献
- ^ ab ブラウワー、アンドリース E.;ヘイマーズ、ウィレム H. (2012)。グラフのスペクトル。大学のテキスト。ニューヨーク州ニューヨーク: スプリンガー ニューヨーク。土井：10.1007/978-1-4614-1939-6。ISBN 978-1-4614-1938-9。
- ^ Haemers, WH; Mohammadian, A.; Tayfeh-Rezaie, B. (2010). 「グラフのラプラシアン固有値の合計について」.線形代数とその応用. 432 (9): 2214–2221. doi : 10.1016/j.laa.2009.03.038 .
- ^ Du, Zhibin; Zhou, Bo (2012). 「グラフのラプラシアン固有値の合計の上限」.線形代数とその応用. 436 (9): 3672–3683. doi : 10.1016/j.laa.2012.01.007 .
- ^ Ganie, Hilal A.; Pirzada, S.; Rather, Bilal A.; Trevisan, V (2020). 「グラフのラプラシアン固有値の合計に関する Brouwer の予想のさらなる発展」.線形代数とその応用. 588 (1): 1–18. doi : 10.1016/j.laa.2019.11.020 . S2CID 213564785.
- ^ Rocha, イスラエル (2020). 「Brouwer の予想は漸近的にほぼ確実に成り立つ」.線形代数とその応用. 597 : 198–205. arXiv : 1906.05368 . doi :10.1016/j.laa.2020.03.019. S2CID 189762363.