グラフラブラシアンの第2固有値を最大にする無向グラフ平均次数が2以下の場合

摘要

与えられた頂点数れと辺数mの下でグラフラブラシアンの第2固有値を最大にする無向グラフを求める問題について考察する．グラフラブラシアンの第2固有値はネットワークマルチエージェントシステムの合意形成における収束の速さを決定する重要な指標である．本報告では，れ=mかつm≦6のとき閉路グラフが第2固有値を最大にすること，n=mかつn≧6のとき星グラフに辺を一つ加えたグラフが第2固有値を最大にすること，閉路グラフが第2固有値を局所的に最大にすることを証明する．%We consider the problem of finding undirected graphs maximizing the second smallest eigenvalue of the graph Laplacian. The second smallest eigenvalue of the graph Laplacian is an important criterion which determines the speed of convergence of a consensus algorithm for networked multi-agent systems. Let n and m denote the numbers of nodes and edges, respectively. We prove in this report that 1) the cycle graph maximizes the second smallest eigenvalue when n = m and n ≦ 6, 2) a graph obtained by adding an edge to the star graph maximizes the second smallest eigenvalue when n = m and n ≧ 6, and 3) the cycle graph locally maximizes the second smallest eigenvalue for any n ≧ 3.