Summary
International Symposium on Nonlinear Theory and Its Applications
2015
Session Number:A4L-D
Session:
Number:A4L-D-3
Complete Multipartite Graphs Maximize Algebraic Connectivity in the Neighborhood Based on 2-Switch
Takuro Fujihara, Norikazu Takahashi,
pp.285-288
Publication Date:2015/12/1
Online ISSN:2188-5079
Summary:
The second smallest eigenvalue of the Laplacian matrix, also known as the algebraic connectivity, is an important quantity for various network systems because it indicates how well the network is connected. The algebraic connectivity also characterizes some dynamic processes on networks such as consensus algorithms for multi-agent networks. In this paper, we prove that the algebraic connectivity of any complete multipartite graph is not less than that of all graphs obtained from it by applying a 2-switch. This is a generalization of the authors' previous result about complete bipartite graphs.