Search

We determine the distance-regular graphs with diameter at least 3 and c 2 ≥ 2 but without induced K 1 , 4 -subgraphs. [ABSTRACT FROM AUTHOR]

A non-complete distance-regular graph is called geometric if there exists a set C of Delsarte cliques such that each edge lies in exactly one clique in C . Let Γ be a geometric distance-regular graph with diameter D ≥ 3 and smallest eigenvalue θ D . In this paper we show that if Γ contains an induced subgraph K 2 , 1 , 1 , then D ≤ − θ D . Moreover, if − θ D − 1 ≤ D ≤ − θ D then D = − θ D and Γ is a Johnson graph. We also show that for ( s , b ) ⁄ ∈ { ( 11 , 11 ) , ( 21 , 21 ) } , there are no distance-regular graphs with intersection array { 4 s , 3 ( s − 1 ) , s + 1 − b ; 1 , 6 , 4 b } where s , b are integers satisfying s ≥ 3 and 2 ≤ b ≤ s . As an application of these results, we classify geometric distance-regular graphs with D ≥ 3 , θ D ≥ − 4 and containing an induced subgraph K 2 , 1 , 1 . [ABSTRACT FROM AUTHOR]

For a distance-regular graph of diameter three Γ, the statement that distance-3 graph Γ 3 of Γ is strongly regular is equivalent to that Γ has eigenvalue −1. There are many distance-regular graphs of diameter 3 having eigenvalue −1, such as the folded 7-cube, generalized hexagons of order ( s , s ) and antipodal nonbipartite distance-regular graphs of diameter 3. In this paper, we show that for a fixed positive integer α ( β , respectively), there are only finitely many distance-regular graphs of diameter 3 having eigenvalue −1 and a 3 = α ( b 1 c 2 = β and a 3 ≠ 0 , respectively). Such distance-regular graphs for small numbers α = 1 , 2 or β = 3 with a 3 ≠ 0 are classified. We show that there are no distance-regular graphs with intersection array { 44 , 35 , 3 ; 1 , 5 , 42 } . Moreover, we classify the distance-regular graphs with diameter 3 and smallest eigenvalue greater than −3. [ABSTRACT FROM AUTHOR]

In 1986, Terwilliger showed that there is a strong relation between the eigenvalues of a distance-regular graph and the eigenvalues of a local graph. In particular, he showed that the eigenvalues of a local graph are bounded in terms of the eigenvalues of a distance-regular graph, and he also showed that if an eigenvalue $$\theta $$ of the distance-regular graph has multiplicity m less than its valency k, then $$-1- \frac{b_1}{\theta +1}$$ is an eigenvalue for any local graph with multiplicity at least $$k-m$$ . In this paper, we are going to generalize the results of Terwilliger to a broader class of subgraphs. Instead of local graphs, we consider induced subgraphs of distance-regular graphs (and more generally t-walk-regular graphs with t a positive integer) which satisfies certain regularity conditions. Then we apply the results to obtain bounds on eigenvalues of t-walk-regular graphs if the girth equals 3, 4, 5, 6 or 8. In particular, we will show that the second largest eigenvalue of a distance-regular graph with girth 6 and valency k is at most $$k-1$$ , and we will show that the only such graphs having $$k-1$$ as its second largest eigenvalue are the doubled Odd graphs. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we study distance-regular graphs with intersection array where are integers satisfying and . Geometric distance-regular graphs with diameter three and have such an intersection array. We first show that if a distance-regular graph with intersection array (1) exists, then is bounded above by a function in . Using this we show that for a fixed integer , there are only finitely many distance-regular graphs of order with smallest eigenvalue , diameter and intersection number except for Hamming graphs with diameter three. Moreover, we will show that if a distance-regular graph with intersection array (1) for exists then . As Gavrilyuk and Makhnev (2013) [9] proved that the case does not exist, this enables us to finish the classification of geometric distance-regular graphs with smallest eigenvalue , diameter and which was started by the first author (Bang, 2013) [1]. [Copyright &y& Elsevier]