Jephian Chin-Hung Lin

Chi-Kwong Li, Jephian C.-H. Lin

For a given graph [Formula: see text], we aim to determine the possible realizable spectra for a generalized (or sometimes referred to as a weighted) Laplacian matrix associated with [Formula: see text]. This new specialized inverse eigenvalue problem is considered for certain families of graphs and graphs on a small number of vertices. Related considerations include studying the possible ordered multiplicity lists associated with stars and complete graphs and graphs with a few vertices. Finally, we present a novel investigation, both theoretically and numerically, regarding the minimum variance over a family of generalized Laplacian matrices with a size-normalized weighting.

Given a graph and one of its weighted Laplacian matrix, a Fiedler vector is an eigenvector with respect to the second smallest eigenvalue. The Fiedler vectors have been used widely for graph partitioning, graph drawing, spectral clustering, and finding the characteristic set. This paper studies how the graph structure can control the possible Fiedler vectors for different weighted Laplacian matrices. For a given tree, we characterize all possible Fiedler vectors among its weighted Laplacian matrix. As an application, the characteristic set can be anywhere on a tree, except for the set containing a single leaf. For a given cycle, we characterize all possible eigenvectors corresponding to the second or the third smallest eigenvalue.