A graph is said to be globally rigid if almost all embeddings of the graph's vertices in the Euclidean plane will define a system of edge‐length equations with a unique (up to isometry) solution. In ...2007, Jackson, Servatius and Servatius characterised exactly which vertex‐transitive graphs are globally rigid solely by their degree and maximal clique number, two easily computable parameters for vertex‐transitive graphs. In this short note we will extend this characterisation to all graphs that are determined by their automorphism group. We do this by characterising exactly which edge‐transitive graphs and distance‐regular graphs are globally rigid by their minimal and maximal degrees.
Let Γ denote a bipartite distance-regular graph with diameter D≥4 and valency k≥3. Let X denote the vertex set of Γ, and let A denote the adjacency matrix of Γ. For x∈X and for 0≤i≤D, let Γi(x) ...denote the set of vertices in X that are distance i from vertex x. Define a parameter Δ2 in terms of the intersection numbers by Δ2=(k−2)(c3−1)−(c2−1)p222. We first show that Δ2=0 implies that D≤5 or c2∈{1,2}.
For x∈X let T=T(x) denote the subalgebra of MatX(C) generated by A,E0⁎,E1⁎,…,ED⁎, where for 0≤i≤D, Ei⁎ represents the projection onto the ith subconstituent of Γ with respect to x. We refer to T as the Terwilliger algebra of Γ with respect to x. By the endpoint of an irreducible T-module W we mean min{i|Ei⁎W≠0}.
In this paper we assume Γ has the property that for 2≤i≤D−1, there exist complex scalars αi, βi such that for all x,y,z∈X with ∂(x,y)=2, ∂(x,z)=i, ∂(y,z)=i, we have αi+βi|Γ1(x)∩Γ1(y)∩Γi−1(z)|=|Γi−1(x)∩Γi−1(y)∩Γ1(z)|. We additionally assume that Δ2=0 with c2=1.
Under the above assumptions we study the algebra T. We show that if Γ is not almost 2-homogeneous, then up to isomorphism there exists exactly one irreducible T-module with endpoint 2. We give an orthogonal basis for this T-module, and we give the action of A on this basis.
Let Γ denote a bipartite distance-regular graph with diameter D≥4 and valency k≥3. Let X denote the vertex set of Γ, and let A denote the adjacency matrix of Γ. For x∈X and for 0≤i≤D, let Γi(x) ...denote the set of vertices in X that are distance i from vertex x. Define a parameter Δ2 in terms of the intersection numbers by Δ2=(k−2)(c3−1)−(c2−1)p222. It is known that Δ2=0 implies that D≤5 or c2∈{1,2}.
For x∈X let T=T(x) denote the subalgebra of MatX(C) generated by A,E0∗,E1∗,…,ED∗, where for 0≤i≤D, Ei∗ represents the projection onto the ith subconstituent of Γ with respect to x. We refer to T as the Terwilliger algebra of Γ with respect to x. By the endpoint of an irreducible T-module W we mean min{i|Ei∗W≠0}.
We find the structure of irreducible T-modules of endpoint 2 for graphs Γ which have the property that for 2≤i≤D−1, there exist complex scalars αi, βi such that for all x,y,z∈X with ∂(x,y)=2,∂(x,z)=i,∂(y,z)=i, we have αi+βi|Γ1(x)∩Γ1(y)∩Γi−1(z)|=|Γi−1(x)∩Γi−1(y)∩Γ1(z)|, in case when Δ2=0 and c2=2. The case when Δ2=0 and c2=1 is already studied by MacLean et al. 15.
We show that if Γ is not almost 2-homogeneous, then up to isomorphism there exists exactly one irreducible T-module with endpoint 2 and it is not thin. We give a basis for this T-module, and we give the action of A on this basis.
In this paper, we study the q-distance matrix for a distance-regular graph and show that the q-distance matrix of a distance-regular graph with classical parameters (D,q,α,β) has exactly three ...distinct eigenvalues, of which one is zero. Moreover, we study distance-regular graphs whose q-distance matrix has exactly one positive eigenvalue.
In this article, we study the order and structure of the largest induced forests in some families of graphs. First we prove a variation of the Delsarte–Hoffman ratio bound for cocliques that gives an ...upper bound on the order of the largest induced forest in a graph. Next we define a canonical induced forest to be a forest that is formed by adding a vertex to a coclique and give several examples of graphs where the maximal forest is a canonical induced forest. These examples are all distance-regular graphs with the property that the Delsarte–Hoffman ratio bound for cocliques holds with equality. We conclude with some examples of related graphs where there are induced forests that are larger than a canonical forest.
In this paper we give a new characterization of the dual polar graphs, extending the work of Brouwer and Wilbrink on regular near polygons. Also as a consequence of our characterization we confirm a ...conjecture of the authors on non-bipartite distance-regular graphs with smallest eigenvalue at most −k/2, where k is the valency of the distance-regular graph, in the case where c2≥3 and a1=1.
We consider the representation of a continuous-time quantum walk in a graph X by the matrix exp(−itA(X)). We provide necessary and sufficient criteria for distance-regular graphs and, more ...generally, for graphs in association schemes to have perfect state transfer. Using these conditions, we provide several new examples of perfect state transfer in simple graphs.
In this paper, we consider the distance-regular graphs Γ whose distance-2 graphs Γ2 are strongly regular. Note that if Γ is bipartite, then its distance-2 graph is not connected. We first show that ...the distance-2 graph of a non-bipartite distance-regular graph with diameter 3 and eigenvalue a2−c3 is strongly regular, and then we give several kinds of classifications of non-bipartite distance-regular graphs with diameter 3 and eigenvalue a2−c3.
PDF
