A class of integral graphs constructed from the hypercube

The $n$-Queens graph, $\mathcal{Q}(n)$, is the graph obtained from a $n\times n$ chessboard where each of its $n^2$ squares is a vertex and two vertices are adjacent if and only if they are in the same row, column or diagonal. In a previous work the authors have shown that, for $n\ge4$, the least eigenvalue of $\mathcal{Q}(n)$ is $-4$ and its multiplicity is $(n-3)^2$. In this paper we prove that $n-4$ is also an eigenvalue of $\mathcal{Q}(n)$ and its multiplicity is at least...

The set $S_{\{i,j\}_{n}^{m}}=\{0,1,2,\ldots,m-1,m,m,m+1,\ldots,n-1,n\}\setminus\{i,j\},\quad 0<i<j\leqslant n$, is called Laplacian realizable if there exists a simple connected graph $G$ whose Laplacian spectrum is $S_{\{i,j\}_{n}^{m}}$. In this case, the graph $G$ is said to realize $S_{\{i,j\}_{n}^{m}}$. In this paper, we completely describe graphs realizing the sets $S_{\{i,j\}_{n}^{m}}$ with $m=1,2$ and determine the structure of these graphs.

Let $\Gamma=(V,E)$ be a graph. The square graph $\Gamma^2$ of the graph $\Gamma$ is the graph with the vertex set $V(\Gamma^2)=V$ in which two vertices are adjacent if and only if their distance in $\Gamma$ is at most two. The square graph of the hypercube $Q_n$ has some interesting properties. For instance, it is highly symmetric and panconnected. In this paper, we investigate some algebraic properties of the graph ${Q^2_n}$. In particular, we show that the graph ${Q^2_n}$...

In this paper we give two characterizations of the $p \times q$-grid graphs as co-edge-regular graphs with four distinct eigenvalues.

This article focuses on finding the eigenvalues of the Laplacian matrix of the comaximal graph $\Gamma(\mathbb Z_n)$ of the ring $\mathbb Z_n$ for $n> 2$. We determine the eigenvalues of $\Gamma(\mathbb Z_n)$ for various $n$ and also provide a procedure to find the eigenvalues of $\Gamma(\mathbb Z_n)$ for any $n> 2$. We show that $\Gamma(\mathbb Z_n)$ is Laplacian Integral for $n=p^\alpha q^\beta$ where $p,q$ are primes and $\alpha, \beta$ are non-negative integers. The algeb...

We establish new bounds on the minimum number of distinct eigenvalues among real symmetric matrices with nonzero off-diagonal pattern described by the edges of a graph and apply these to determine the minimum number of distinct eigenvalues of several families of graphs and small graphs.

For an $n \times n$ matrix $A$, let $q(A)$ be the number of distinct eigenvalues of $A$. If $G$ is a connected graph on $n$ vertices, let $\mathcal{S}(G)$ be the set of all real symmetric $n \times n$ matrices $A=[a_{ij}]$ such that for $i\neq j$, $a_{ij}=0$ if and only if $\{i,j\}$ is not an edge of $G$. Let $q(G)={\rm min}\{q(A)\,:\,A \in \mathcal{S}(G)\}$. Studying $q(G)$ has become a fundamental sub-problem of the inverse eigenvalue problem for graphs, and characterizing ...

The minimum number of distinct eigenvalues, taken over all real symmetric matrices compatible with a given graph $G$, is denoted by $q(G)$. Using other parameters related to $G$, bounds for $q(G)$ are proven and then applied to deduce further properties of $q(G)$. It is shown that there is a great number of graphs $G$ for which $q(G)=2$. For some families of graphs, such as the join of a graph with itself, complete bipartite graphs, and cycles, this minimum value is obtained....

This is a continuation of the article with the same title. In this paper, the family H is the same as in the previous paper "On Graphs with the Smallest Eigenvalue at Least $-1-\sqrt{2}$, part I". The main result is that a minimal graph which is not an H -line graph, is just isomorphic to one of the 38 graphs found by computer.

We study a family of graphs related to the $n$-cube. The middle cube graph of parameter $k$ is the subgraph of $Q_{2k-1}$ induced by the set of vertices whose binary representation has either $k-1$ or $k$ number of ones. The middle cube graphs can be obtained from the well-known odd graphs by doubling their vertex set. Here we study some of the properties of the middle cube graphs in the light of the theory of distance-regular graphs. In particular, we completely determine th...