Eigenvalue interlacing and weight parameters of graphs (Q1300913): Difference between revisions

Suppose a positive eigenvector belonging to the largest eigenvalue of a graph is normalized in such a way that its smallest coordinate is equal to 1. Assigning coordinates of such a vector to vertices as weights, maximal values of the sum of squares of weights of vertices in independent (and some other interesting) vertex subsets are studied. Some known results (e.g. bounds for the Shannon capacity and the chromatic number) are improved and in some cases extended to hold not only for regular graphs. Interlacing theorems for graph eigenvalues are used in the proofs. Similar results are obtained with the Laplacian matrix of a graph but without introducing vertex weights.