On the multiplicity of Laplacian eigenvalues and Fiedler partitions
For researchers in spectral graph theory, this work offers incremental theoretical insights into eigenvalue multiplicities and graph partitioning.
The paper studies the relation between Laplacian eigenvalues and graph structure for (m,k)-stars and l-dependent graphs, providing conditions for eigenvalue multiplicities and showing that vertex set reduction preserves eigenvalues with reduced multiplicity. It also relates these results to Fiedler spectral partitioning.
In this paper we study two classes of graphs, the (m,k)-stars and l-dependent graphs, investigating the relation between spectrum characteristics and graph structure: conditions on the topology and edge weights are given in order to get values and multiplicities of Laplacian matrix eigenvalues. We prove that a vertex set reduction on graphs with (m,k)-star subgraphs is feasible, keeping the same eigenvalues with reduced multiplicity. Moreover, some useful eigenvectors properties are derived up to a product with a suitable matrix. Finally, we relate these results with Fiedler spectral partitioning of the graph. The physical relevance of the results is shortly discussed.