Eigenvalue interlacing and weight parameters of graphs

DOI10.1016/S0024-3795(98)10238-0MaRDI QIDQ1300913zbMATH OpenWikidataFDO

Authors V. Pereyra

Publication date 2 September 1999

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.0367

zbMATH Keywords

chromatic number eigenvector interlacing Laplacian matrix regular graphs Shannon capacity vertex weights

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: Eigenvalue interlacing is a versatile technique for deriving results in algebraic combinatorics. In particular, it has been successfully used for proving a number of results about the relation between the (adjacency matrix or Laplacian) spectrum of a graph and some of its properties. For instance, some characterizations of regular partitions, and bounds for some parameters, such as the independence and chromatic numbers, the diameter, the bandwidth, etc., have been obtained. For each parameter of a graph involving the cardinality of some vertex sets, we can define its corresponding weight parameter by giving some "weights" (that is, the entries of the positive eigenvector) to the vertices and replacing cardinalities by square norms. The key point is that such weights "regularize" the graph, and hence allow us to define a kind of regular partition, called "pseudo-regular," intended for general graphs. Here we show how to use interlacing for proving results about some weight parameters and pseudo-regular partitions of a graph. For instance, generalizing a well-known result of Lov'asz, it is shown that the weight Shannon capacity

T h e t a^{*}

of a connected graph

G

, with

n

vertices and (adjacency matrix) eigenvalues

l a m b d a_{1} > l a m b d a_{2} g e ... g e l a m b d a_{n}

, satisfies

Thetale Theta^* le frac{|vecnu|^2}{1-frac{lambda_1}{lambda_n}}

where

T h e t a

is the (standard) Shannon capacity and

v e c n u

is the positive eigenvector normalized to have smallest entry 1. In the special case of regular graphs, the results obtained have some interesting corollaries, such as an upper bound for some of the multiplicities of the eigenvalues of a distance-regular graph. Finally, some results involving the Laplacian spectrum are derived. spectrum are derived.

Review text

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.

Recommendations

Cites work

Cited in

(33)

This page was built for publication: Eigenvalue interlacing and weight parameters of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1300913)