Search

In order to define the discrete-time quantum walks, we divide the vertex set of a graph by two partitions and give a time evolution operator by a product of two local unitary operators on each partition. In this paper, we make such partitions from a Hoffman graph, which gives generalization of line graphs, and study a staggered walk. We first show that the square of the time evolution operator of the Grover walk is unitarily equivalent to that of the staggered walk on the generalized line graph induced from a Hoffman graph. Furthermore, we focus on the periodicity of quantum walks and show that the staggered walk on the generalized line graph is periodic whenever the Grover walk on the original graph is periodic by using the unitary equivalence. This work is the first trial to develop the relation between quantum walks and Hoffman graphs.

In this paper, we show that every connected signed graph with smallest eigenvalue strictly greater than $-2$ and large enough minimum degree is switching equivalent to a complete graph. This is a signed analogue of a theorem of Hoffman. The proof is based on what we call Hoffman's limit theorem which we formulate for Hermitian matrices, and also the extension of the concept of Hoffman graph and line graph for the setting of signed graphs., Comment: 20 pages, minor revision

In this paper, we will give a structure theory for graphs with fixed smallest eigenvalue. In order to do this, the concept of Hoffman graph (as introduced by Woo and Neumaier) is used. Our main result states that for fixed positive integer λ and any graph G with smallest eigenvalue at least −λ, there exist dense induced subgraphs Q 1 , … , Q c in G such that each vertex lies in at most λ Q i 's and almost all edges of G lie in at least one of the Q i 's.

In 1977, Hoffman gave a characterization of graphs with smallest eigenvalue at least $-2$. In this paper we generalize this result to graphs with smaller smallest eigenvalue. For the proof, we use a combinatorial object named Hoffman graph, introduced by Woo and Neumaier in 1995. Our result says that for every $\lambda \leq -2$, if a graph with smallest eigenvalue at least $\lambda$ satisfies some local conditions, then it is highly structured. We apply our result to graphs which are cospectral with the Hamming graph $H(3,q)$, the Johnson graph $J(v, 3)$ and the $2$-clique extension of grids, respectively., Comment: 26 pages

There are many results on graphs with the smallest eigenvalue at least -2. As a next step, A. J. Hoffman proposed to study graphs with the smallest eigenvalue at least -1 - √2. In order to deal with such graphs, R. Woo and A. Neumaier defined a new generalization of line graphs which depends on a family of isomorphism classes of graphs with a distinguished coclique. They proved a theorem analogous to Hoffman's, using a particular family consisting of four isomorphism classes. In this paper, we deal with a generalization based on a family H smaller than the one which they dealt with, yet including generalized line graphs in the sense of Hoffman. The main result is that the cover of an H-line graph with at least 8 vertices is unique.

In this paper, we give a combinatorial characterization of the special graphs of fat Hoffman graphs containing $\mathfrak{K}_{1,2}$ with smallest eigenvalue greater than -3, where $\mathfrak{K}_{1,2}$ is the Hoffman graph having one slim vertex and two fat vertices., Comment: 21+5 pages

We investigate fat Hoffman graphs with smallest eigenvalue at least -3, using their special graphs. We show that the special graph S(H) of an indecomposable fat Hoffman graph H is represented by the standard lattice or an irreducible root lattice. Moreover, we show that if the special graph admits an integral representation, that is, the lattice spanned by it is not an exceptional root lattice, then the special graph S(H) is isomorphic to one of the Dynkin graphs A_n, D_n, or extended Dynkin graphs A_n or D_n., Comment: 23 pages, minor revision. Example 3.8 added

In this paper, we present the first application of Hoffman graphs for spectral characterizations of graphs. In particular, we show that the 2-clique extension of the $(t+1)\times (t+1)$-grid is determined by its spectrum when $t$ is large enough. This result will help to show that the Grassmann graph $J_2(2D,D)$ is determined by its intersection numbers as a distance regular graph, if $D$ is large enough.