BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Jack Koolen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
In 1979, Neumaier gave a bound on $λ$ in terms of $m$ and $μ$, where $-m$ is the smallest eigenvalue of a primitive strongly regular graph, unless the graph in question belongs to one of the two infinite families of strongly regular graphs. We improve this result. We also indicate how our methods can be used to give an alternate derivation of Bruck's Completion Theorem for orthogonal arrays.
In this paper, we study the non-bipartite distance-regular graphs with valency k and having a smallest eigenvalue at most -k/2.
Juriśič et al. conjectured that if a distance-regular graph $Γ$ with diameter $D$ at least three has a light tail, then one of the following holds: 1.$a_1 =0$; 2.$Γ$ is an antipodal cover of diameter three; 3.$Γ$ is tight; 4.$Γ$ is the halved $2D+1$-cube; 5.$Γ$ is a Hermitian dual polar graph $^2A_{2D-1}(r)$ where $r$ is a prime power. In this note, we will consider the case when the light tail corresponds to the eigenvalue $-\frac{k}{a_1 +1}$. Our main result is: Theorem Let $Γ$ be a non-bipartite distance-regular graph with valency $k \geq 3$ , diameter $D \geq 3$ and distinct eigenvalues $θ_0 > θ_1 > \cdots > θ_D$. Suppose that $Γ$ is $2$-bounded with smallest eigenvalue $θ_D = -\frac{k}{a_1 +1}$. If the minimal idempotent $E_D$, corresponding to eigenvalue $θ_D$, is a light tail, then $Γ$ is the dual polar graph $^2A_{2D-1}(r)$, where $r$ is a prime power. As a consequence of this result we will also show: Theorem Let $Γ$ be a distance-regular graph with valency $k \geq 3$, diameter $D \geq 2$, $a_1 =1$ and $θ_0 > θ_1 > \cdots > θ_D$. If $c_2 \geq5$ and $θ_D = -k/2$, then $c_2 =5$ and $Γ$ is the dual polar graph $^2A_{2D-1}(2)$.
A realisation of a metric $d$ on a finite set $X$ is a weighted graph $(G,w)$ whose vertex set contains $X$ such that the shortest-path distance between elements of $X$ considered as vertices in $G$ is equal to $d$. Such a realisation $(G,w)$ is called optimal if the sum of its edge weights is minimal over all such realisations. Optimal realisations always exist, although it is NP-hard to compute them in general, and they have applications in areas such as phylogenetics, electrical networks and internet tomography. In [Adv. in Math. 53, 1984, 321-402] A.~Dress showed that the optimal realisations of a metric $d$ are closely related to a certain polytopal complex that can be canonically associated to $d$ called its tight-span. Moreover, he conjectured that the (weighted) graph consisting of the zero- and one-dimensional faces of the tight-span of $d$ must always contain an optimal realisation as a homeomorphic subgraph. In this paper, we prove that this conjecture does indeed hold for a certain class of metrics, namely the class of totally"=decomposable metrics whose tight-span has dimension two. As a corollary, it follows that the minimum Manhattan network problem is a special case of finding optimal realisations of two-dimensional totally-decomposable metrics.
We give a structural classification of edge-signed graphs with smallest eigenvalue greater than -2. We prove a conjecture of Hoffman about the smallest eigenvalue of the line graph of a tree that was stated in the 1970s. Furthermore, we prove a more general result extending Hoffman's original statement to all edge-signed graphs with smallest eigenvalue greater than -2. Our results give a classification of the special graphs of fat Hoffman graphs with smallest eigenvalue greater than -3.
It is known that a distance-regular graph with valency $k$ at least three admits at most two Q-polynomial structures. % In this note we show that all distance-regular graphs with diameter four and valency at least three admitting two $Q$-polynomial structures are either dual bipartite or almost dual imprimitive. By the work of Dickie \cite{Dickie} this implies that any distance-regular graph with diameter $d$ at least four and valency at least three admitting two $Q$-polynomial structures is, provided it is not a Hadamard graph, either the cube $H(d,2)$ with $d$ even, the half cube ${1}/{2} H(2d+1,2)$, the folded cube $\tilde{H}(2d+1,2)$, or the dual polar graph on $[^2A_{2d-1}(q)]$ with $q\ge 2$ a prime power.
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.
We investigate the behavior of electric potentials on distance-regular graphs, and extend some results of a prior paper. Our main result, Theorem 4, shows(together with Corollary 3) that if distance is measured by the electric resistance between points then all points are close to being equidistant on a distance-regular graph with large valency. A number of auxiliary results are also presented.
In this paper, we classify the connected non-bipartite integral graphs with spectral radius three.