Vertex types in some lexicographic products of graphs

Abstract

Let M = [mij] be a symmetric matrix, or equivalently, a weighted graph (Formula presented.) whose edge ij has the weight (Formula presented.). The eigenvalues of mij are the eigenvalues of M. We denote by (Formula presented.) the principal submatrix of M obtained by deleting from M both the ith row and the ith column. If μ is an eigenvalue of M, and thus of (Formula presented.), of multiplicity (Formula presented.), then vertex i of k ≥ 1 is a downer, or a neutral, or a Parter vertex, depending whether the multiplicity of μ in (Formula presented.) or, equivalently, in (Formula presented.), is k−1, k, or k+1, respectively. In this paper, for a fixed μ, we consider vertex types according to the above classification in graphs which are generalized lexicographic products of an arbitrary graph over cliques and co-cliques, or connected regular graphs. In addition, we add some comments on constructions of large families of cospectral and integral graphs.