Linear algebra and its applications

Vol. 302-303, p. 45-61

DOI: 10.1016/S0024-3795(99)00015-4

Date of publication: 1999-12-01

Linear algebra and its applications

Vol. 298, p. 115-141

Date of publication: 1999-09

Abstract:

Let C be a connected graph with vertex set V, adjacency matrix A, positive eigenvector and corresponding eigenvalue 0. A natural generalization of distance-regularity around a vertex subset C V , which makes sense even with non-regular graphs, is studied. This new concept is called pseudo-distance-regularity, and its definition is based on giving to each vertex u 2 V a weight which equals the corresponding entry u of and “regularizes” the graph. This approach reveals a kind of central symmetry which, in fact, is an inherent property of all kinds of distance-regularity, because of the distance partition of V they come from. We come across such a concept via an orthogonal sequence of polynomials, constructed from the “local spectrum” of C, called the adjacency polynomials because their definition strongly relies on the adjacency matrix A. In particular, it is shown that C is “tight” (that is, the corresponding adjacency polynomials attain their maxima at 0) if and only if C is pseudo-distance-regular around C. As an application, some new spectral characterizations of distance-regularity around a set and completely regular codes are given.]]>

Linear algebra and its applications

Vol. 297, num. 1-3, p. 23-56

DOI: 10.1016/S0024-3795(99)00113-5

Date of publication: 1999-08

Linear algebra and its applications

Vol. 291, num. 1-3, p. 83-102

DOI: 10.1016/S0024-3795(98)10227-6

Date of publication: 1999-04-15

Linear algebra and its applications

Vol. 290, p. 275-301

Date of publication: 1999-03

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 s~aow 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 Lovfisz, it is shown that the weight Shannon capacity 6)* of a connected graph F, with n vertices and (adjacency matrix) eigenvalues 2j > )~2 ~> '" ~> 2,, satisfies o~

Linear algebra and its applications

Vol. .., num. 290, p. 145-166

Date of publication: 1999-01