Summary
the 2014 International Symposium on Nonlinear Theory and its Applications
2014
Session Number:B2L-D
Session:
Number:B2L-D4
On Graphs that Locally Maximize Algebraic Connectivity in the Space of Graphs with the Fixed Degree Sequence
Takuro Fujihara, Norikazu Takahashi,
pp.353-356
Publication Date:2014/9/14
Online ISSN:2188-5079
Summary:
The second smallest eigenvalue of the Laplacian matrix, also known as the algebraic connectivity, is an important measure that characterizes the performance of some dynamic processes on the network. In this paper, we study the problem of finding graphs that locally maximize the algebraic connectivity in the space of graphs with the fixed degree sequence. We first prove that complete bipartite graphs are such graphs. We next find some 3-regular graphs that locally maximize the algebraic connectivity by using a local search algorithm based on 2-switch.