TY - CHAP
TI - Generalized Graph Laplacians, Degree Sequences and Majorization Theorems
AB - Brualdi and Solheid (1986) proposed the following general problem, which became one of the classic problems of spectral graph theory: "Given a set G of graphs, find an upper bound for the spectral radius in this set and characterize the graphs in which the maximal spectral radius is attained." Now there exist extensive literature that characterizes such extremal graphs for quite a couple of such sets. Moreover, the problem has been generalized to the Dirichlet matrices and (signless) Laplacian matrix of graphs. One particular class is that of graphs which a prescribed degree sequence. Many of the proofs for such results apply graph perturbations that increase or decrease the spectral radius. In graph classes like trees one may eventually arrive at a graph with maximum or minimum spectral radius. As a by-product we get majorization results for the given degree sequences, that is, we get an ordering of such sequences with respect to the extremal eigenvalue in the corresponding class. In this talk we want to present a framework for deriving such results for generalized Laplacians that works for connected graph with cyclomatic number at most 2.
AF - 20th Conference of the International Linear Algebra Society (ILAS)
PP - Leuven
PY - 2016-01-01
AU - Leydold, Josef
ER -