頂点数と辺数の制約下で代数的連結度が最大となる完全多部グラフに関する考察

摘要

ラプラシアン行列の 2 番目に小さい固有値である代数的連結度は，グラフがいかに強く連結しているかを示す重要な指標である．また，代数的連結度はマルチエージェントネットワークの合意形成や結合振動子の同期のようなネットワーク上のダイナミクスの性能を特徴づける．例えばマルチエージェントネットワークの代表的な合意形成アルゴリズムの収束速度は，ネットワークの代数的連結度が大きいほど速いことが知られている．本稿では，頂点数と辺数の制約下で代数的連結度を最大にするグラフの構造について考察する．はじめに小規模なグラフを対象にグラフ列挙アルゴリズムに基づく全探索を行い，頂点数と辺数の制約下で代数的連結度が最大となるグラフを求める．次に正則な完全多部グラフに着目し，それらが同じ頂点数と辺数からなるグラフの中で代数的連結度を最大にすることを理論的に証明する．