Search

The universal adjacency matrix U of a graph Γ, with adjacency matrix A, is a linear combination of A, the diagonal matrix D of vertex degrees, the identity matrix I, and the all-1 matrix J with real coefficients, that is, U = c 1 A + c 2 D + c 3 I + c 4 J , with c i ∈ R and c 1 ≠ 0. Thus, in particular cases, U may be the adjacency matrix, the Laplacian, the signless Laplacian, and the Seidel matrix. In this paper, we develop a method for determining the universal spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not). As an example, the method is applied to give an efficient algorithm to determine the characteristic polynomial of the Laplacian matrix of the symmetric squares of odd cycles, together with closed formulas for some of their eigenvalues. [ABSTRACT FROM AUTHOR]

We study regular graphs whose distance-2 graph or distance-1-or-2 graph is strongly regular. We provide a characterization of such graphs Γ (among regular graphs with few distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex, where d+1 is the number of different eigenvalues of Γ. This can be seen as another version of the so-called spectral excess theorem, which characterizes in a similar way those regular graphs that are distance-regular. [ABSTRACT FROM AUTHOR]

In this article we follow the study of the hierarchical product of graphs, an operation recently introduced in the context of networks. A well-known example of such a product is the binomial tree which is the (hierarchical) power of the complete graph on two vertices. An appealing property of this structure is that all the eigenvalues are distinct. Here we show how to obtain a graph with this property by applying the hierarchical product. In particular, we propose a generalization of the binomial tree and study some of its main properties. [ABSTRACT FROM AUTHOR]

We prove that Moore digraphs, and some other classes of extremal digraphs, are weakly distance-regular in the sense that there is an invariance of the number of walks between vertices at a given distance. As weakly distance-regular digraphs, we then compute their complete spectrum from a ‘small’ intersection matrix. This is a very useful tool for deriving some results about their existence and/or their structural properties. For instance, we present here an alternative and unified proof of the existence results on Moore digraphs, Moore bipartite digraphs and, more generally, Moore generalized p -cycles. In addition, we show that the line digraph structure appears as a characteristic property of any Moore generalized p -cycle of diameter D   ≥  2 p . [ABSTRACT FROM AUTHOR]

An outindependent subgraph of a graph Γ, with respect to an independent vertex subset C ⊂⃒   V , is the subgraph ΓC induced by the vertices in V ∖   C . We study the case when Γ is strongly regular, where the results of de Caen [1998, The spectra of complementary subgraphs in a strongly regular graph. European Journal of Combinatorics , 19 (5), 559–565.], allow us to derive the whole spectrum of ΓC . Moreover, when C attains the Hoffman–Lovász bound for the independence number, ΓC is a regular graph (in fact, distance-regular if Γ is a Moore graph). This article is mainly devoted to study the non-regular case. As a main result, we characterize the structure of ΓC when C is the neighborhood of either one vertex or one edge. [ABSTRACT FROM AUTHOR]