1,721,006 research outputs found
The distance-regular graphs such that all of its second largest local eigenvalues are at most one
No full textIn this paper, we classify distance-regular graphs such that all of its second largest local eigenvalues are at most one. Also we discuss the consequences for the smallest eigenvalue of a distance-regular graph. These extend a result by the first author, who classified the distance-regular graphs with smallest eigenvalue -1 - b(1)/2. (C) 2011 Elsevier Inc. All rights reserved.X1154sciescopu
On geometric distance-regular graphs with diameter three
Full text linkIn this paper we study distance-regular graphs with intersection array {(t + 1)s. ts. (t - 1)(s + 1 - psi); 1, 2, (t + 1)psi} (1) where s. t. psi are integers satisfying t >= 2 and 1 = 2, there are only finitely many distance-regular graphs of order (s, t) with mallest eigenvalue -t -1, diameter D = 3 and intersection number c(2) = 2 except for Hamming graphs with diameter three. Moreover, we will show that if a distance-regular graph with intersection array (1) for t = 2 exists then (s, psi) = (15, 9). As Gavrilyuk and Makhnev (2013)[9] proved that the case (s, psi) = (15, 9) does not exist, this enables us to finish the classification of geometric distance-regular graphs with smallest eigenvalue -3, diameter D >= 3 and c(2) >= 2 which was started by the first author (Bang, 2013)[1]. (C) 2013 Elsevier Ltd. All rights reserved.X1121Ysciescopu
On the connectedness of the complement of a ball in distance-regular graphs
No full textAn important property of strongly regular graphs is that the second subconstituent of any primitive strongly regular graph is always connected. Brouwer asked to what extent this statement can be generalized to distance-regular graphs. In this paper, we show that if gamma is any vertex of a distance-regular graph I" and t is the index where the standard sequence corresponding to the second largest eigenvalue of I" changes sign, then the subgraph induced by the vertices at distance at least t from gamma, is connected.X1166sciescopu
Hyperbolic bridged graphs
No full textGiven a connected graph G, we take, as usual, the distance xy between any two vertices x, y of G to be the length of some geodesic between x and y. The graph G is said to be delta-hyperbolic, for some 3 : 0, if for all vertices x, y, u, v in G the inequality xy + uv :5 max{xu + yv, xv + yu} + delta holds, and G is bridged if it contains no finite isometric cycles of length four or more. In this paper, we will show that a finite connected bridged graph is 1-hyperbolic if and only if it does not contain any of a list of six graphs as an isometric subgraph. (C) 2002 Elsevier Science Ltd. All rights reserved.X1141sciescopu
The vertex-connectivity of a distance-regular graph
No full textThe vertex-connectivity of a distance-regular graph equals its valency. (C) 2008 Dr Andries E. Brouwer. Published by Elsevier Ltd. All rights reserved.X1118sciescopu
Shilla distance-regular graphs
No full textA Shilla distance-regular graph Gamma (say with valency k) is a distance-regular graph with diameter 3 such that as second-largest eigenvalue equals a(3). We will show that a(3) divides k for a Shilla distance-regular graph Gamma, and for Gamma we define b = b(Gamma) = k/a(3) In this paper we will show that there are finitely many Shilla distance-regular graphs Gamma with fixed b(Gamma) >= 2 Also, we will classify Shilla distance-regular graphs with b(Gamma) = 2 and b(Gamma) = 3 Furthermore, we will give a new existence condition for distance-regular graphs, in general. (C) 2010 Elsevier Ltd. All rights reservedX111912sciescopu
Some interlacing results for the eigenvalues of distance-regular graphs
No full textIn this paper we study the absolute values of non-trivial eigenvalues of a distance-regular graph and find that these usually have large absolute value. We also give a motivation concerning a conjecture of Bannai and Ito.X11sciescopu
Cospectral graphs and the generalized adjacency matrix
No full textLet J be the all-ones rnatrix, and let A denote the adjacency matrix of a graph. An old result of Johnson and Newman states that if two graphs are cospectral with respect to yJ - A for two distinct values of y, then they are cospectral for all y. Here we will focus on graphs cospectral with respect to yJ - A for exactly one value (y) over cap of (y) over cap. We call such graphs (y) over cap -cospectral. It follows that is a rational number, and we prove existence of a pair of (y) over cap -cospectral graphs for every rational. In addition, we generate by computer all (y) over cap -cospectral pairs on at most nine vertices. Recently, Chesnokov and the second author constructed pairs of (y) over cap -cospectral graphs for all rational (y) over cap is an element of (0, 1), where one graph is regular and the other one is not. This phenomenon is only possible for the mentioned values of, and by computer we find all Such pairs of (y) over cap -cospectral graphs on at most eleven vertices. (C) 2006 Elsevier Inc. All rights reserved.X1116sciescopu
On distance-regular graphs with smallest eigenvalue at least -m
No full textA non-complete geometric distance-regular graph is the point graph of a partial linear space in which the set of lines is a set of Delsarte cliques. In this paper, we prove that for a fixed integer m >= 2, there are only finitely many non-geometric distance-regular graphs with smallest eigenvalue at least -m, diameter at least three and intersection number c(2) >= 2. (C) 2010 Elsevier Inc. All rights reserved.X111311sciescopu
A relationship between the diameter and the intersection number c (2) for a distance-regular graph
No full textIn this paper we will look at the relationship between the intersection number c (2) and the diameter of a distance-regular graph. We also give some tools to show that a distance-regular graph with large c (2) is bipartite, and a tool to show that if k (D) is too small then the distance-regular graph has to be antipodal.X1142sciescopu
- …
